정렬 1(버블, 선택, 삽입)

정렬 알고리즘

정렬 알고리즘이란 순서가 뒤섞인 데이터들을 오름차순 또는 내림차순으로 변경시켜주는 알고리즘이다.

ex [2, 4, 3, 5, 1]의 데이터를 가졌을 때 오름차순 정렬 후 [1, 2, 3, 4, 5]로 데이터의 순서가 변경된다.

 

오늘 사용할 정렬들은 버블정렬, 선택정렬, 삽입정렬으로 시간복잡도 n의 2제곱을 가지는 알고리즘이지만 간단하고 직관적인 정렬방법들로 다음에 배울 정렬보다 기초가 되는 알고리즘이다.

버블정렬

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식이다. 

[2, 4, 3, 5, 1] 데이터를 가질 때 우선 첫번 째 인덱스와 두번째 인덱스의 수를 비교 (2와 4) 4가 더 작은 수이기 떄문에 순서가 변하지 않습니다. 다음은 두번 째 인덱스와 세번째 인덱스의 수를 비교(4, 3) 3이 더 작은 수 임으로 3이 앞으로 오게 됩니다. 지금까지 [2, 3, 4]의 순서로 정렬 됩니다. 이렇게 마지막 인덱스까지 비교하면 [2, 3, 4, 1, 5]가 됩니다.

가장 큰 수인 5가 제일 뒤로 오게 된다.

다음은 정렬할 데이터보다 1 작은 수 까지 반복해준다.

이 과정을 계속 반복하면 아래와 같이 된다.

 

ex)

[2, 4, 3, 5, 1] -> [2, 3, 4, 5, 1] -> [2, 3, 4, 5, 1] -> [2, 3, 4, 1, 5]

[2, 3, 4, 1, 5] -> [2, 3, 4, 1, 5] -> [2, 3, 1, 4, 5] 

[2, 3, 1, 4, 5] -> [2, 1, 3, 4, 5] 

[1, 2, 3, 4, 5] 

 

 

선택정렬

선택 정렬은 순서대로 비교하다가 가장 작은 수를 '선택'해 1번째에 오게 하고 그다음으로 작은 수를 2번 째에 그 다음을 3번째에... 이런식으로 마지막까지 정렬하는 방식이다.

 

ex)

[2, 4, 3, 5, 1]  [2, 4, 3, 5, 1]  [2, 4, 3, 5, 1]  [2, 4, 3, 5, 1] 순서로 비교 가장 작은 수를 첫번째로 변경 [1, 4, 3, 5, 2]

[1, 4, 3, 5, 2]  [1, 4, 3, 5, 2]  [1, 4, 3, 5, 2]  순서로 비교 가장 작은 수를 두번째로 변경 [1, 2, 3, 5, 4]

[1, 2, 3, 5, 4]  [1, 2, 3, 5, 4]  순서로 비교 가장 작은 수가 3이기 때문에 그대로 [1, 2, 3, 5, 4]

[1, 2, 3, 5, 4] 마지막으로 5, 4를 비교해 작은수를 4번째로 오게해 [1, 2, 3, 4, 5]가 된다.

 

 

삽입정렬

삽입 정렬은 전체에서 하나씩 올바른 위치에 '삽입' 하는 방식이다. 선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만, 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식이다.

 

ex)

[2, 4, 3, 5, 1] 에서 [2]가 있으면 앞에서부터 비교해 4를 올바른 위치에 삽입한다. [2, 4]

[2, 4, 3, 5, 1] 에서 [2, 4]가 있으면 앞에서부터 비교해 3을 올바른 위치에 삽입한다. [2, 3, 4]

[2, 4, 3, 5, 1] 에서 [2, 3, 4]가 있으면 앞에서부터 비교해 5을 올바른 위치에 삽입한다. [2, 3, 4, 5]

[2, 4, 3, 5, 1] 에서[2, 3, 4, 5] -> [1, 2, 3, 4, 5]