Sorting algorithm1. Selection, Bubble, Insertion, Quick

Sort algorithm 1

0. Swap function

void swap(int *a, int *b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

-모든 정렬함수에서 arr의 각 원소의 주소값을 받아서 swap 했다.

 

 

1. Selection sort

void selectionsort(int a[],int n) {
    for(int i=0; i<n;i++){
        for(int j = i+1; j<n;j++){
            if(a[i]<a[j]){swap(&a[i], &a[j]);}
        }
    }
}

1. 전체 원소중 가장 큰 원소(작은원소)를 찾아 제일 앞에 위치시키는 방법

 

- 배열의 크기(n)가 9일경우 

1. 0과 1~8까지 비교 , 가장 큰 원소를 찾아 0번째 자리와 교환

2. 1과 2~8까지 비교 , 가장 큰 원소를 찾아 1번째 자리와 교환

3. 이를 반복한다.

 

2. 시간복잡도는 O(n^2) 이다.

- 내부 for문 n-1 + n-2 + n-3 + ... + 0 = n(n-1)/2

 

 

2. Bubble sort

void bubblesort(int a[], int n){
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(a[j]<a[j+1]){swap (&a[j], &a[j+1]);}
        }
    }
}

1. 인접한 원소와 비교하면서 정렬하는 방법

 

-배열의 크기가 5일경우

1. 외부 for문 0

2. 01 비교, 12 비교, 23비교, 34비교하여 if문 만족시 swap (내림차순 기준 가장 작은 값이 후방에 위치, n n n n 1)

3. 외부 for문 1

4. 01 비교, 12 비교, 23비교하여 if문 만족시 swap(그다음 작은 값이 후방에 위치, n n n 2 1)

5. 위의 과정을 반복한다.

 

2. Selection sort 와 마찬가지로 시간복잡도는 O(n^2) 이다.

 

 

 

3. Insertion sort

void insertionsort(int a[], int n){
    int k, j;
    for(int i=1;i<n;i++){
        k = a[i];
        for(j=i-1;j>=0;j--){
            if(a[j]<k){a[j+1] = a[j];}
            else break;
        }
        a[j+1] = k;
    }
}

1. key값을 정한다 key값은 배열의 1번값 부터 하나씩 정해진다.

2. key값과 key값이전의 원소들을 비교한다.

 

-배열의 크기가 5인경우

1. 1번 원소값이 key

2. 내부 루프에서 0번 값을 조사한다. key값(원래1번)이 0번보다 크면 0번값이 1번값이 된다.  

3. 루프가 끝났으므로 key값이 0번값으로 삽입된다.(j == -1 상태로 내부 반복문 탈출 a[0]에 key대입)

4. 2번 원소값이 key

5. 내부 루프에서 1번값을 조사한다. key값(원래2번)이 1번보다 크면 1번값이 2번값으로 밀려난다.

6. 내부 루프에서 0번값을 조사한다. key값(원래2번)이 0번보다 작으면 else문으로 반복문을 탈출한다.

7. 반복문 탈출 후 j+1위치에 key값 대입(a[1] 에 key대입)

8. 3번 원소값이 key 이고 위과정을 반복한다.

 

3. 마찬가지로 n^2의 최악의 시간복잡도를 가진다, 최선일경우는 n이다.(원래부터 정렬된 배열)

 

4. Quick sort

void quicksort(int a[], int left, int right){
    if(left<right){
        int pivot = partition(a, left, right);        //리턴받은 pivot값을 정의한다.
        quicksort(a, left, pivot - 1);            /*pivot 값기준 좌, 우 그룹에 대해 재귀로 진행*/
        quicksort(a, pivot + 1, right);
    }
}

 

Step 1.

1. index0 을 pivot으로 결정한다.(무작위 값이어도 가능하다.)

2. left 에서부터 index번호를 증가 , right 에서부터 index번호를 감소시킨다.

3. 각각의 값들을 아래 조건에 따라 pivot 과 비교한다.(내림차순 기준)

- 증가하는 index의 경우 값이 pivot 보다 작을 경우 

- 감소하는 index의 경우 값이 pivot 보다 클 경우

4. 두 값을 do while문으로 체크해 if(left+a < right -b) 일경우 두 원소를 바꾼다.5. 이를 증가index와 감소 index가 같아질 때까지 한다.

최초 pivot (index0)

left+1

left+2

...

right-2

right-1

right

Step 2.이후 pivot값과 같아진 값을 교체한다. 이후 배열을 pivot 값을 기준으로 이분할한다.(pivot값 리턴)

left1

...

right1

pivot (index0 이었음)

left2

...

right2

Step 3. 리턴된 pivot값을 기준으로 좌 우 그룹에 대해 위 과정을 반복한다.

 

- 아래는 Step 1 의 partition 함수에 대한 이해이다.

int partition(int a[], int left, int right){
    int pivot = a[left];    //무작위값 (여기선 왼쪽값에 대해 pivot 값 선정)
    int upper = left;         //upper을 left(최초값 0)
    int downer = right+1;     //downer를 right+1 값으로 지정

    while(upper<downer){
        do {
            upper ++;
        }while(upper<=right && a[upper]>pivot);
        do{
            downer --;
        }while(downer>=left && a[downer]<pivot);
        /*low 와 high를 각각 증가, 감소시키면서 pivot값과의 상대적 위치가 잘못된 값을 찾는다.*/

        if(upper<downer){       //dowhile 문으로 low high 를 각각 증감 시키다 pivot 값을 지나쳐 교차할 경우를 방지하는 if 문
            swap(&a[upper], &a[downer]);    
        }
    }
    swap(&a[left], &a[downer]);
    /*pivot 위치의 값과 high 위치의 값을 swap 한다, 위치상으로 pivot을 기준으로 크기에 따른 array elements가 두 그룹으로 분할된다.*/

    return downer;  //pivot값 리턴을 의미한다.
}

- Partition함수에 대한 랜덤 배열 26789134 에 대한 함수 최초 1회 실행시 값변화

Step
A	2	6	7	8	9	1	3	4
par.	pivot(left)	++upper	++upper	++upper	++upper	upper		downer
B	2	6	7	8	9	4	3	1
par.	pivot(left)					upper	new downer	downer
C	2	6	7	8	9	3	4	1
par.	pivot(left)					upper	downer	--downer
D	4	6	7	8	9	3	2	1
par.	그룹 1 new pivot 1	그룹 1	그룹 1	그룹 1	그룹 1	그룹 1	return 값	그룹2 new pivot 2

Time complexity

1. 최선의 경우

Quick sort의 경우 그룹이 정확히 2분할 됨(index 8 기준 4/4, 2/2/2/2, 1/1/1/1/1/1/1/1)이반복되면 이는 완전 이진 트리를 그리는것과 비슷하다. 호출의 횟수는 완전 이진트리의 깊이를 구하는 것과 동일하다. 최 하위 노드가 n개라고 가정했을 때 깊이는 log₂n 임을 알 수 있다. 각각의 호출에서 n개의 원소들을 비교하기 때문에 n번의 연산이 수행된다. 즉 최선의 경우 Time complexity는 O(n*log₂n) 을 만족한다.

 

2. 최악의 경우

위의 Partition 예시처럼, 1 : n-1 의 index를 가지는 그룹으로 분할되는 상황이 반복될 경우, 깊이는 n이 될것이다.

(1 : n-1 / 1: n-2 / 1: n-3 /. ....../ 1:n-(n-1)

이경우 Time complexity는 O(n^2) 이다.