퀵 정렬(quick sort)

개념

- 배열의 값에서 Pivot(기준 값)을 선택 후, Pivot을 기준으로 집합을 분할하여 정렬하는 알고리즘(분할정복)

- 정렬이 된 값의 좌측 집합과 우측 집합은 값이 완전히 정렬이 된 상태.

- 데이터가 이미 정렬되어있는 경우, 분할정복 이점이 없고 삽입 정렬이 더 좋은 성능이 나올 수 있음.

private void quickSort(int[] list, int start, int end) {
  /*
  * start 시작 원소위치
  * end 마지막 원소위치
  */
  int pivot, i, j, temp;

  if(start >= end) { // 배열의 원소가 1개인 경우 종료 - 재귀종료 조건
  	return;
  }

  pivot = start; //기준 값은 첫번째 원소로 설정
  i = start+1; //기준 값보다 큰 값을 pivot 우측부터 배열 끝까지 탐색
  j = end; //기준 값보다 작은 값을 배열 끝에서 좌측으로 탐색

  //오른쪽->왼쪽(작은 값 탐색)으로 탐색한 위치가 왼쪽->오른쪽(큰 값 탐색)으로 탐색한 위치보다 작은 위치가 될 때까지 반복(엇갈릴때까지 반복)
  while(i <= j) { 
  	//1. 탐색수행 범위(왼쪽->오른쪽 큰값 탐색) 
  	while(i <= end && list[i] <= list[pivot]) { //왼쪽은 pivot 값보다 큰 값 탐색
		i++;
  	}
  	//2. 탐색수행 범위(오른쪽->왼쪽 작은값 탐색)
  	while (j > start && list[j] >= list[pivot]) { //오른쪽은 pivot 값보다 작은 값 탐색, 탐색값이 배열범위를 넘어가지않도록 시작위치로 탐색범위 제한
  		j--;
  	}
  	//3. 위치 변경(pivot보다 큰 값, 작은 값의 위치 검사(i, j))
  	if(i > j) { //현재 엇갈린 상태면, pivot 값과 j 값 교체(pivot값과 작은값 위치 서로 교체)
  		temp = list[j];
  		list[j] = list[pivot];
  		list[pivot] = temp;
  	} else { //엇갈린 상태가 아니라면, i와 j 값 교체(큰값과 작은값 위치 서로 교체)
  		temp = list[i];
  		list[i] = list[j];
  		list[j] = temp;
	}
  }
  //탐색 위치가 엇갈려서 밖으로 나온 경우, 해당 pivot 값을 기준으로 좌측 집합과 우측 집합의 정렬 수행		
  //좌측 그룹
  quickSort(list, start, j-1);
  //우측 그룹
  quickSort(list, j+1, end);
}

 

※ 평균 시간복잡도는 O(N*log N)

※ 최악 시간복잡도는 O(N^2)