퀵 정렬

https://www.youtube.com/watch?v=gBcUO_6JXIA&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=6

https://m.blog.naver.com/ndb796/221226813382

5. 퀵 정렬(Quick Sort)

퀵 정렬은 선택 정렬, 버블 정렬, 삽입 정렬에 비해 가장 빠르게 원소를 정렬할 수 있다.

 

. 

 

#include <iostream>

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

void show(){
  int i;
  for(i=0; i<number; i++){
    printf("%d ", data[i]);
  }
}

void quickSort(int *data, int start, int end){
  if(start >= end){ // 원소가 1개인 경우 그대로 두기
    return;
  }
  
  int key=start;
  int i= start+1;
  int j=end;
  int tmp;

  while(i<= j){ //  엇갈릴 때까지 반복
    while(i<= end && data[i] <= data[key]){ // 키 값보다 큰 값을 만날때까지
      i++;
    }
    while(j>start && data[j]>= data[key]){ // 키 값보다 작은 값을 만날때까지
      j--;
    }
    if(i>j){ // 현재 엇갈린 상태면 키 값과 교체
      tmp =data[j];
      data[j]= data[key];
      data[key]=tmp;
    }
    else { // 엇갈리지 않았다면 i와 j를 교체
      tmp = data[i];
      data[i] = data[j];
      data [j] = tmp;
    }
  }
  
  quickSort(data, start, j-1);
  quickSort(data, j+1, end);
}



int main() {
  quickSort(data, 0, number-1);
  show();
  return 0;
}