Quick sort와 Bubble sort

오늘은 정렬의 가장기본인 bubble 그리고 quick에 대해 알아볼 것임...


1. Bubble sort

한 자리씩 양쪽의 숫자를 비교하여 큰 쪽을 오른쪽(혹은 왼쪽)으로 정렬해 오름차순 혹은 내림차순으로 정리

모든 숫자의 좌우를 한 번씩 전부 비교 즉 모든 경우의 수를 다 확인하는 과정이라 연산이 아주 느림

적은 숫자의 배열에 사용하는 것이 유리함 (건틀렛에서 16개의 순서를 비교하기에는 충분하지만 500+단위의 인벤토리를 정렬하기에는 부적절)


핵심 : 좌우의 교체

if(argument0[j] > argument0[j+1])

{

temp = argument0[j];

argument0[@j] = argument0[j+1];

argument0[@j+1] = temp;

}

일단 argument자리에 정렬하려는 array를 받음...

array에서 j자리의 숫자가 j+1자리의 숫자보다 크면 j자리의 숫자를 j+1의 숫자로 대체하고 j+1의 자리는 j자리로 옮김

이 과정을 모든 자리에서 반복하며 j자리에 가장 작은 숫자가 오고 맨 끝에는 가장 큰 수가 오게 됨 (부등호의 방향을 바꾸면 반대로 됨)

결장의 용병을 공격 순서로 정리해 하단에 표기하는 기능 등의 구현이 가능함

그러나 수백 단위의 용병이 보관된 인벤토리를 bubble 방식으로 정렬하면 불필요한 연산이 늘어나 입력 지연, 프레임드랍이 일어날 수 있음...



2. Quick sort

quick sort는 약간 응용된 알고리즘임

기본은 똑같이 array 안에서 숫자의 위치를 바꾸는 과정을 거치는 것인데 좌우를 전부 비교해서 만약 왼쪽(혹은 오른쪽)이 크면 좌우를 바꾸고... 무수히 반복해서 항상 좌 혹은 우가 크도록 정렬하는 과정이 bubble sort라면

quick sort는 pivot을 기점으로 큰 숫자는 모두 오른쪽, 작은 숫자는 모두 왼쪽으로 가르는 방법을 반복하는 것임

1~10의 숫자가 랜덤하게 섞여있는 상태일 때 : 가장 오른쪽의 숫자를 기점으로 좌우 정렬을 반복함

맨 오른쪽이 6이었음 -> 왼쪽으로 1~5, 오른쪽으로 7~10을 가름(단 여전히 순서는 랜덤임)

다시 1~5까지 있는 그룹에서 가장 오른쪽을 고르고 좌우 정렬을 시작하고 7~10에서도 좌우정렬을 시작함

결과적으로 pivot의 왼쪽에는 작은 숫자가, 오른쪽에는 큰 숫자가 오는데 다시 왼쪽, 오른쪽 무리의 pivot을 기점으로도 같은 일이 일어나므로

각 소그룹의 왼쪽은 작은 수, 오른쪽은 큰 수가 됨

하위 pivot의 가장 오른쪽 숫자(가장 큰 수)도 상위 pivot과 비교해서는 작은 숫자이기 때문에 결과적으로 작은 숫자부터(혹은 큰 숫자부터) 나란히 배열이 일어남




입력을 하나만 받는 bubble 방식과 달리 quick은 세 개를 받음 각각 array, 첫 배열, 마지막 배열임

pivot = array[max](max = array의 크기)으로 설정하고 배열 중 마지막 숫자를 기준으로 삼아 정렬을 반복하는 것...

코드는 복잡하니깐않쓰겠음... 정렬할 단위가 커지더라도 충분히 대응할 수 있는 방식임...