Sort Problem

Algorithm

---

Sort Algorithm Summary:

internal sorts.

• Insertion sort, selection sort, bubblesort, shaker sort.
• Quicksort, mergesort, heapsort, samplesort, shellsort.
• Solitaire sort, red-black sort, splaysort, Dobosiewicz sort, psort, ...

external sorts.

• Poly-phase mergesort, cascade-merge, oscillating sort.

radix sorts.

• Distribution, MSD, LSD.
• 3-way radix quicksort.

parallel sorts.

• Bitonic sort, Batcher even-odd sort.
• Smooth sort, cube sort, column sort.
• GPUsort.

1. Bubble Sort

         exchange the neighbor nodes

            void bubbleSort(Comparable<Object>[] a):
                    int k = a.length;
                    boolean flag = true;
                    while(flag):
                        flag = false;
                        for(int i=0;i<k-1;k++):
                            if(a[i]>a[i+1]):
                                int tmp = a[i];
                                a[i] = a[i+1];
                                a[i+1] = tmp;
                                flag = true;
                        k--;                        

2. Insertion Sort

        insert a[i] into a[0] - a[i-1]

            for(int i=0;i<a.length;i++):
                for(int j=i;j>0;j--):
                    if(a[j]<a[j-1])
                        int tmp = a[j-1];
                        a[j-1] = a[j];
                        a[j] = tmp;

3. Selection Sort

        select the minimal number from lowest index and exchange to current index

            for(int i=0;i<a.length;i++)
                int minIndex = i; // be aware! the index not the value;
                for(int j = i+1;j<a.length;j++)
                    if(a[j]<a[min])
                        min = j;
                //exchange min & i 
                int tmp = a[i];
                a[i] = a[min]; 
                a[min] = a[i];

4. Merge Sort

            // extra space
            int[] aux;
            // separate array into two parts each time
            sort(int[] a, int lo, int hi):
                if(lo>hi)
                    return;
                int mid = lo+(hi-lo)/2;
                sort(a,lo,mid);
                sort(a.mid+1,hi);
                merge(a,lo,mid,hi);
            merge(int[] a, int lo, int mid; int hi);
                int i = lo, j = mid;
                for(int k = lo; i<hi;k++):
                    aux[k] = a[k];
                for(int k = lo; i<hi;k++):
                    if(i>mid)
                        a[k] = aux[j++];
                    else if(j>hi)
                        a[k] = aux[i++];
                    else if(aux[j]>aux[i])
                        a[k] = aux[i++];
                    else
                        a[k] = aux[j++];

5. Quick Sort

        // partition
        // recursion sort

            sort(int[] a, int lo, int hi):
                if(lo>hi):
                    return;
                int j = partition(a,lo,hi);
                sort(a,lo,j-1);
                sort(a,j+1,hi);
            partition(int[] a, int lo, int hi):
                int i = lo, j = hi+1;
                int v = a[lo]; // pivot
                while(true):
                    // 左右交换向前 向后
                    // 三种条件 跳出循环！
                    while(a[++i]<v):
                            if(i==hi): break;
                    while(a[--j]>v):
                            if(j==lo): break;
                    if(i>=j): break;
                    // 交换 i j点
                    exch(a,i,j);
                exch(a,lo,j);
                return j; //切分点

6. Shell Sort

            int N = a.length;
            int h = 1;
            while(h<N/3): // shell from large to small
                h = h * 3 + 1;
            while(h>=1):
                for(int i=h; i<N; i+=h):
                    if(a[i]<a[i-h]):
                        int tmp = a[i];
                        int j = i-h;
                        while(j>=0&&a[j]>tmp):
                            a[j+h] = a[j];
                            j-=h;
                        a[j+h] = tmp;
                h = (h-1)/3;

7. Conclusion

Shellsort.
• Warmup: easy way to break the N2 barrier.
• Embedded systems.

Mergesort.
• Java sort for objects.
• Perl, Python stable sort.

Quicksort.
• Java sort for primitive types.
• C qsort, Unix, g++, Visual C++, Python.

Cracking Code Interview:

9.1 Merge two sorted two array: A is larger than B

                void merge(int a[], int b[], int n, int m):
                        int i = n - 1; // for A last index
                        int j = m - 1; // for B last index
                        int k = n + m - 1; // for total index on A
                        while(i>=0&&j>=0):
                            if(a[i]>b[j]):
                                a[k--] = a[i--];
                            else
                                a[k--] = b[j--];
                        while(j>=0); // notice only b can remain the elements which need to be placed into A
                            a[k--] = b[j--];

9.2 Sort an array of strings

                class AnagramComparator implements Comparator<String>:
                        String sortChars(String s):
                            char[] content = s.toCharArray();
                            Arrays.sort(content);
                            return new String(content);
                        int compare(String s1, String s2):
                            return sortChars(s1).compareTo(sortChars(s2));
                main:
                        String[] strings  -> Arrays.sort(array, new AnagramComparator());

9.4 think about >2GB file to sort