퀵 정렬(quick sort)

- 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모으는 함수를 작성.

- 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복.

- 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함.

 

=================================

index  :  0     1      2     3    4    5     6    7 

value  : 49   97   53    5   33  65  62  51

=================================

pivot선택 : (index : 0, value : 49)

p1 (1회)

pivot   - (index : 0, value : 49)

[left]   - (index : 3, value : 5), (index : 4, value : 33) 

[right] -(index : 1, value : 97), (index : 2, value : 53), (index : 5, value : 65), (index : 6, value : 62), (index : 7, value : 51)      

p2(2회)

p1의 [left]

pivot   - (index : 3, value : 5)

[left]   - 

[right] -(index : 4, value : 33) 

p1의 [right]

pivot   - (index : 1, value : 97)

[left]   - (index : 2, value : 53), (index : 5, value : 65), (index : 6, value : 62), (index : 7, value : 51)   

[right] -

. . . (이런식으로 데이터 수가 1개가 될 때까지...재귀함수 => 분할) 

분할과정이 끝나면 합치기(정복)

...(앞부분 과정은 생략)

[left]    - (index : 3, value : 5), (index : 4, value : 33) 

[pivot] - (index : 0, value : 49)

[right]  - (index : 7, value : 51), (index : 2, value : 53), (index : 6, value : 62), (index : 5, value : 65), (index : 1, value : 97) 

[merge] - (index : 3, value : 5), (index : 4, value : 33) + (index : 0, value : 49) + (index : 7, value : 51), (index : 2, value : 53), (index : 6, value : 62), (index : 5, value : 65), (index : 1, value : 97) 

 

[원리 시각화]

https://www.hackerearth.com/practice/algorithms/sorting/quick-sort/visualize/

Quick Sort visualize | Sorting | Algorithms | HackerEarth

#코드

import sys
 
 
def quickSort(arr, start, end):
  if start >= end:
    return
  else:
    pivot = start
    left  = start + 1
    right = end 
    while left <= right:
      # pivot보다 큰 데이터를 찾을 때까지 반복
      while left <= end and arr[left] <= arr[pivot]: # 처음 경우 : arr[left] = 7, arr[pivot] = 5 이므로 while문을 타지 않는다.
        left += 1
      # pivot보다 작은 데이터를 찾을 때까지 반복
      while right > start and arr[right] >= arr[pivot]: # 처음 경우 : arr[right] = 8, arr[pivot] = 5 이므로 while문을 돈다.
        right -= 1
      
      if left > right: # 위치가 엇갈렸다면 작은 데이터와 피벗의 위치를 교체
         arr[right], arr[pivot] = arr[pivot], arr[right]
      else: # 위치가 엇갈리지 않았다면 작은 데이터와 큰 데이터의 위치를 교체
        arr[left], arr[right] = arr[right], arr[left]
      
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quickSort(arr, start, right-1)
    quickSort(arr, right+1, end) 
  
 
if __name__ == "__main__":
  
  input = sys.stdin.readline
  
  n   = int(input())
  arr = list(map(int, input().split()))
  
  quickSort(arr, 0, n-1)
  print(*arr)

#입력
10
5 7 9 0 3 1 6 2 4 8

 

#코드

import sys 
 
def quickSort(arr):
  if len(arr) <= 1:
    return arr
  else:
    pivot = arr[0]  # pivot은 첫 번째 원소
    tail  = arr[1:] # pivot을 제외한 리스트
    
    left_side  = [x for x in tail if x <= pivot] # 분할된 왼쪽부분
    right_side = [x for x in tail if x > pivot]  # 분할된 오른쪽부분 
    
    return quickSort(left_side) + [pivot] + quickSort(right_side)
    
if __name__ == "__main__":
  
  input = sys.stdin.readline
  
  n   = int(input())
  arr = list(map(int, input().split()))
  
  print(*quickSort(arr)) 

 

#코드

import random
 
def qsort(data):
  if len(data) <= 1:
    return data  
  left, right = list(), list()
  pivot = data[0]
  for i in range(1, len(data)):
    if pivot > data[i]: #왼쪽
      left.append(data[i])
    else: #오른쪽
      right.append(data[i])
  return qsort(left) + [pivot] + qsort(right)
 
 
 
data_list = random.sample(range(100), 10)
print(data_list)
data_list = qsort(data_list)
print(data_list)

*시간복잡도 : O(nlogn)

*최악 : O(n^2)

 

// 자바 코드

import java.util.*;
import java.io.*;
 
public class Main{
  
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static int n;
  static int[] arr;
  
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    arr = new int[n];
    for(int i=0; i<n; i++) arr[i] = Integer.parseInt(st.nextToken());
    
    quickSort(0, n-1);
    
    StringBuilder sb = new StringBuilder();  
    for(int i=0; i<n; i++) {
      sb.append(String.valueOf(arr[i]) + " ");
    }
    
    bw.write(String.valueOf(sb));
    
    br.close();
    bw.flush();
    bw.close();
    
  }
  
  
  // arr을 start부터 end까지 퀵정렬 하는 함수.
  static void quickSort(int start, int end) {
    
    if(start>=end) return;
    
    int pivot   = arr[start];
    int[] left  = new int[n];
    int[] right = new int[n];
    
    int leftCnt  = getLeft(start+1, end, pivot, left);
    int rightCnt = getRight(start+1, end, pivot, right);
    
    for(int i=0; i<leftCnt; i++) {
      arr[start+i] = left[i];
    }
    arr[start+leftCnt] = pivot;
    for(int i=0; i<rightCnt; i++) {
      arr[start+leftCnt+1+i] = right[i];
    }
    
    quickSort(start, start+leftCnt-1); // -1은 pivot을 뺀값.
    quickSort(start+leftCnt+1, end);
    
  }
  
  
  // arr의 start부터 end까지 숫자들 중에서
  // pivot 보다 작거나 같은 값을 result에 채우는 함수.
  // 또한, 작거나 같은 원소의 개수를 반환한다.
  static int getLeft(int start, int end, int pivot, int[] result){
    
    int idx=0;
    for(int i=start; i<=end; i++) {
      if(arr[i]<=pivot) {
        result[idx++] = arr[i];
      }
    }
    
    return idx;
  }
  
  
  // arr의 start부터 end까지 숫자들 중에서
  // pivot 보다 큰 값을 result에 채우는 함수.
  // 또한, 큰 원소의 개수를 반환한다.
  static int getRight(int start, int end, int pivot, int[] result){
    
    int idx=0;
    for(int i=start; i<=end; i++) {
      if(arr[i]>pivot) {
        result[idx++] = arr[i];
      }
    }
    
    return idx;
  }
  
}