Discussion :

[spyder14]

Bonsoir,

voila j'ai programmé le tri rapide et le tri par insertion et je voudrai programmer une version optimisée du tri rapide qui est la suivante : si mon sous tableau est de taille inférieure à 16 j'utilise le tri par insertion sinon j'utilise le tri rapide. Mon problème est que je ne vois pas comment faire, quelqu'un pourrait m'aider svp?

Merci

[Franck Dernoncourt]

Branche conditionnelle ?

Exemple en C# issu de http://megocode3.wordpress.com/2008/01/28/8/ :

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
/* The Quicksort is one of the fastest sorting algorithms for sorting large lists of data.  The Insertion sort is a fast sorting algorithms for sorting very small lists that are already somewhat sorted.  We combine these two algorithms to come up with a very simple and effective method for sorting large lists.
 
We start our sort by using a Quicksort.  The Quicksort on average runs in O(n log(n)) time but can be as slow as O(n2) if we try to sort a list that is already sorted and use the left most element as our pivot.  If you are unfamiliar with the quicksort here is a Wikipedia article describing the algorithm: <a href="http://en.wikipedia.org/wiki/Quicksort" target="_blank">http://en.wikipedia.org/wiki/Quicksort</a>
 
As the Quicksort works, it breaks down our list into smaller and smaller lists.  Once the lists become small enough that an Insertion sort becomes more efficient then the Quicksort we will switch to the Insertion sort to finish off the job.  Think of it as grinding away with the Quicksort then polishing it off with the Insertion sort once most of the work has been done.
 
Here is a code sample of a combined Quicksort and Insertion sort algorithm in C#.
*/
 
class Quicksort
{
    public void Sort(int[] list, int start, int end)
    {
        if (start < end)
        {
            // This is where we switch to Insertion Sort!
            if ((end – start) < 9)
            {
                this.InsertionSort(list, start, end + 1);
            }
            else
            {
                int part = this.partition(list, start, end);
                this.Sort(list, start, part – 1);
                this.Sort(list, part + 1, end);
            }
        }
    }
    public void InsertionSort(int[] list, int start, int end)
    {
        for (int x = start + 1; x < end; x++)
        {
            int val = list[x];
            int j = x – 1;
            while (j >= 0 && val < list[j])
            {
                list[j + 1] = list[j];
                j–;
            }
            list[j + 1] = val;
        }
    }
    private int partition(int[] list, int leftIndex, int rightIndex)
    {
        int left = leftIndex;
        int right = rightIndex;
        int pivot = list[leftIndex];
        while (left < right)
        {
            if (list[left] < pivot)
            {
                left++;
                continue;
            }
            if (list[right] > pivot)
            {
                right–;
                continue;
            }
            int tmp = list[left];
            list[left] = list[right];
            list[right] = tmp;
            left++;
        }
        return left;
    }
}