빠른 정렬 및 최적화

빠른 정렬은 분치 사상을 바탕으로 하는 정렬 알고리즘으로 핵심은 구분과 귀속이며 별도의 보조 공간이 필요하지 않다.
빠른 배열의 기본 실현

def  partition(ls,l,r):  #  ， 
    middle = l  #  ， 
    while l ls[middle] and l=r:    #  
        return ls
    m = partition(ls,l,r)
    print('ls {}  l {}  m {}  r {}'.format(ls,ls[l],ls[m],ls[r])) 
    doSort(ls,l,m-1)
    doSort(ls,m+1,r)

#l = [6,2,7,3,11,11,11,8,9,1,11,5]
l = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
doSort(l,0,len(l)-1)
print(' return_list {}'.format(l))

1. 임의성 유지
절분 원소는 랜덤으로 유지해야 한다. 즉doSort는 모든 하위 그룹에 대해 동일시되기 때문에 우리는doSort 앞에서 수조 원소를 혼란시킬 수 있다
스피드 스테이션은 왜 랜덤이 필요합니까?

l = [5,1,9,3,7,4,8,6,2]
$ python QuickSort.py
after one partition ls:[4, 1, 2, 3, 5, 7, 8, 6, 9] l:4 m:5 r:9
after one partition ls:[3, 1, 2, 4, 5, 7, 8, 6, 9] l:3 m:4 r:4
after one partition ls:[2, 1, 3, 4, 5, 7, 8, 6, 9] l:2 m:3 r:3
after one partition ls:[1, 2, 3, 4, 5, 7, 8, 6, 9] l:1 m:2 r:2
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:6 m:7 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:8 m:8 r:9
 return_list [1, 2, 3, 4, 5, 6, 7, 8, 9]

여기서 우리는 qs시간의 복잡도가 가장 좋은 상황을 토론한다. 즉, 매번 구분한 후에 수조를 반으로 나눌 수 있다. 이때 분치 귀속 C(n)=2C(n/2)+n을 만족시킨다
그 중에서 2C 아래 n/2는 두 개의 하위 그룹을 정렬하는 원가를 표시하고, N은 원소와 모든 원소를 나누어 비교하는 원가가 C(n)~nlogn을 얻기 어렵지 않다는 것을 나타낸다
최악의 경우

l = [1,2,3,4,5,6,7,8,9]
$ python QuickSort.py
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:1 m:1 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:2 m:2 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:3 m:3 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:4 m:4 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:5 m:5 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:6 m:6 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:7 m:7 r:9
after one partition ls:[1, 2, 3, 4, 5, 6, 7, 8, 9] l:8 m:8 r:9
 return_list [1, 2, 3, 4, 5, 6, 7, 8, 9]

최악의 경우 시간 복잡도 구분 비교 횟수는 n, n-1, n-2,...1 시간 복잡도 O (n^2)
수조가 거의 질서정연한 상황에서 시간 복잡도가 O(n^2)로 퇴화되는 것을 피하기 위해서는 수조의 임의성을 유지하는 것이 중요하다. 우리는 첫 번째 구분 전에 수조 원소를 무작위로 혼란시킨다.

import random 
l =[1,2,3,4,5,6,7,8,9]
random.shuffle(l)
doSort(l,0,len(l)-1)

2. 소수점 그룹 시 삽입 정렬로 전환

#   
import random  
#  
def  partition(ls,l,r):  #  ， 
    middle = l  #  ， 
    while l ls[middle] and l=l and not ls[j]<= ls[j+1]:
            ls[j],ls[j+1] = ls[j+1],ls[j] # 
            j -=1
# ★★★ : 
def  QuickSort(ls,l,r):
    M = 5  #    5  15 
    if l + M>=r :   #  
        insertSort(ls,l,r)
        return ls
    m = partition(ls,l,r)
    QuickSort(ls,l,m-1)
    QuickSort(ls,m+1,r)

l = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48,6,3,23,11,12,13,62,55,134,2324343,33,98,1,6]
random.shuffle(l)    #  ★★★ : 
QuickSort2(l,0,len(l)-1)
print(' return_list {}'.format(l))

3. 네덜란드 국기 문제 3등분 빠른 배열 실현
네덜란드 국기 문제 실현

  //  
    public int[] partition(int[] arr, int l, int r, int p) {
        int less = l - 1;
        int more = r + 1;
        while (l < more) {
            if (arr[l] < p) {
                swap(arr, ++less, l++);
            } else if (arr[l] > p) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        return new int[]{less + 1, more - 1};  
 //    less   more
    }

네덜란드 국기 문제 빠른 배열 실현 (융합 랜덤, 3등분, 삽입 정렬)

//    
    public void quickSort(int[] arr) {
        if (arr == null || arr.length == 1) {
            return;
        }
        QS(arr, 0, arr.length - 1);
    }

    //  
    public void QS(int[] arr, int l, int r) {
        if (l > r) return;
        int M = 10;   //   5 15 
        if (l + M >= r) insertSort(arr, l, r);
        // Math.random() * N    [0 N)  
        swap(arr, l + (int) (Math.random() * (r - l + 1)), r);  //  
        int[] p = partition(arr, l, r);
        QS(arr, l, p[0] - 1);
        QS(arr, p[1] + 1, r);
    }

    //  
    public int[] partition(int[] arr, int l, int r) {
        int less = l - 1;
        int more = r + 1;
        while (l < more) {
            if (arr[l] < arr[r]) {
                swap(arr, ++less, l++);
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        return new int[]{less + 1, more - 1};   //  
    }

    //     
    public void insertSort(int[] arr, int l, int r) {
        if (arr == null || arr.length == 1) return;

        for (int i = l + 1; i <= r; i++) {
            int j = i - 1;
            while (j >= l && arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                j--;
            }
        }
        return;
    }

    //   
    public void swap(int[] arr, int i, int j) {
        if (arr[i] != arr[j]) {
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }
    }