퀵 정렬

 

시간 복잡도

퀵 정렬의 시간복잡도는 O(N*logN)

 

코드 & 작동원리

 

#include<bits/stdc++.h>
using namespace std;

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

void quickSort(int *data, int start, int end){
	if (start >= end) { //원소가 1개인 경우 
		return; 
	}
	
	int key = start; //키는 첫번째 원소
	int i = start + 1;
	int j = end;
	int temp;
	
	while(i <= j) { // 엇갈릴 때까지 반복
		while(data[i] >= data[key]) {//키 값보다 큰 값을 만날때까지  
			i++;
		}
		while(data[j] <= data[key] && j > start) {//키 값보다 작은 값을 만날때까지
			j--;
		}
		if(i > j) {
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		}
		else {
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}
	
	quickSort(data, start, j-1);
	quickSort(data, j+1, end);
}
//line 13, 14: i와 j는 인덱스 역할
//line 13: i는 키 값 이후에 인덱스 
//line 14: j는 마지막부터 시작할 인덱스 
//line 21: j>start, 오른쪽에서부터 값을 찾을때 스타트 값 전까지만 찾아도 됨
//line 18: 오른쪽으로 갈 때는 오른쪽을 기준으로 왼쪽에서 오는 숫자와 엇갈리면 교체하기에 필요없음 

int main()
{
	quickSort(data, 0, number - 1);
	for(int i=0; i<number; i++){
		cout << data[i] << ' ';
	}
	return 0;
}
/*
퀵 정렬은 대표적인 분할 정복 알고리즘으로 평균 속도가 (N*logN)
log2N -> N이 1,000,000일 때 20
logxN => 밑을 x으로 뒀을 때 N이 되는 수 

퀵 정렬 최악의 시간 복잡도는 O(N^2)
정렬된 숫자의 경우 분할 정복이 의미가 없기에 N개의 숫자를 모두 검사해야한다
때문에 선택, 버블, 삽입과 같은 시간 복잡도가 된다 

키 값을 기준으로 키 값보다 큰 값, 작은 값을 찾음
큰 값은 시작위치부터 찾음, 작은 값은 마지막 위치부터 찾음

값을 찾았을 때 작은 값이 큰 값보다 앞에 위치하면 키 값과 위치를 바꿈(엇갈렸다) 
원래 키 값보다 왼쪽에 있는 값은 모두 키 값보다 작음  
키 값과 비교하여 작은 값이 안나오면 이 또한 엇갈린 것으로 자기자신을 자신과 바꿈(사실상 그대로)
데이터가 한 개면 그대로 => 처음 키 값 앞에 있는 숫자는 정렬됨 

엇갈린게 아니라면 큰 값이 작은 값보다 앞에 있는 경우니 서로 바꿈

※엇갈렸을 때는 원래 키 값을 기준으로 집합을 만들어 같은 원리로 실행※ 
*/

//line 18, line 21을 바꾸면 내림차순, 오름차순으로 바꿀 수 있다.