[C언어] 자료구조 -정렬(sorting) - 4, 퀵정렬

정말 정렬이 빨라서

Quick이다.

퀵정렬... 앞서 말한 정렬보다 훨씬 빠르다.

정렬알고리즘은 항상 N이 커질 때 그 진가를 발한다.

 

---

 

1,3,5,7,9,10,8,6,4,2

 

Divide & Conquer를 이용, 분할 정복을 이용한 알고리즘이다.

Pivot, 피벗을 설정해서 정렬의 기준을 잡고 시작한다.

++보통 첫번째 원소를 Pivot으로 정한다.

ex) (1)   3,5,7,9,10,8,6,4,2

 

즉, 피벗보다 큰 숫자를 왼쪽부터 찾기시작하고

피벗보다 작은 숫자를 오른쪽부터 찾는다.

** 만약 엇갈리지 않고 찾는다면 그 숫자의 위치를 서로 바꿔준다.

 

(1)   /3/,5,7,9,10,8,6,4,2

3찾았고

1보다 작은 걸 찾지 못했다. 결국 1에 도달한다.

 

 

작은 숫자의 인덱스가 큰숫자의 인덱스보다 작아지면 피벗자리와 작은 숫자의 자리를 바꾼다.

(엇갈리면)

 

++/3/ 보다 왼쪽에 있는 1에 도착함.

-> 첫번째 정렬 똑같음. 1과 1을 바꿔도 같음

1,3,5,7,9,10,8,6,4,2

 

즉, 엇갈렸을 때 피벗의 의미는 그 숫자는 정렬되었다는 의미다.

-> 피벗값의 왼쪽에는 피벗보다 작은 값이 존재, 피벗값의 오른쪽에는 피벗보다 큰 값이 존재.

 

그러면 왼쪽 값과 오른쪽 값이 나누어졌으면

그 나누어진 곳에서 다시 퀵정렬를 수행한다.

 

...끝~

 

쉽다.

한 번 보자

#include <stdio.h>

int number = 10;
int data[] = {1,3,5,7,9,10,8,6,4,2};

//start는 첫번째 element
//end는 마지막 element


void quickSort(int* data, int start, int end){
	if (start >= end){ // 원소가 1개면 정렬할 필요 없음. 
    	return;
        }
    int key = start // 해당 그룹의 첫번째 원소
    int i = start + 1, j = end, temp;
    
    while(i <= j){ // i는 첫번째 인덱스인데. j보다 커지면 중단
    	while(i <= end && data[i] <= data[key]){ // key 값보다 큰 값을 만날 때까지 반복
        	i++; // 인덱스를 올리며 찾는다.
        }
        while(i > start && data[j] >= data[key]){ // key 값보다 작은 값을 만날 때 까지 반복
        	j--; //인덱스를 내려가며 찾는다.
        
        }
        if (i > j) { // 엇갈리면 피벗(key)와 교체
        	temp = data[j]
            data[j] = data[key]
            data[key] = temp;
        }
        else{ // 엇갈리지 않았으면 i와 j만 교체
    	    temp = data[i]
            data[i] = data[j]
            data[j] = temp;
        
        }
    }
    quickSort(data, start, j-1); // 피벗 왼쪽 그룹
    quickSort(data, j+1, end); // 피벗 오른쪽 그룹
}

int main(void){
	quickSort(data, 0, number - 1); // 배열의 첫번째 인덱스, 마지막 인덱스를 넣어준다.
    return 0;
}