[백엔드TIL] 버블정렬과 삽입정렬
- Bubble Sort [거품 정렬]
거품 정렬은 아마 정렬 방식 중 가장 쉽게 생각할 수 있는 알고리즘 중 하나일 것이다.
두 개의 인접한 원소를 비교하여 정렬하는 방식이다.
왜 Bubble 이라는 이름이 붙었는지 찾아보니 정렬 과정에서 원소의 이동이 마치 거품이 수면위로 올라오는 것 같다고 해서 거품(Bubble) 이라는 이름이 붙었다고 한다...
정렬 방식 중 가장 쉬우니 일단 거품 정렬에 대한 특징만 짚고 넘어가보자.
거품 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다.
그리고 이전에 다뤘던 선택 정렬과는 달리 거품 정렬은 앞에서부터 차례대로 비교하기 때문에 '안정 정렬'이기도 하다.
- 정렬 방법
거품 정렬의 전체적인 과정은 이렇다. (오름차순을 기준으로 설명)
1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다.
2. 현재 원소가 다음 원소보다 크면 원소를 교환한다.
3. 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교한다.
즉, 그림으로 보면 다음과 같은 과정을 거친다.
이 때, 각 라운드를 진행 할 때마다 뒤에서부터 한 개씩 정렬되기 때문에, 라운드가 진행 될 때마다 한 번씩 줄면서 비교하게 된다.
한마디로 정리하자면 이렇다.
총 라운드는 배열 크기 - 1 번 진행되고,
각 라운드별 비교 횟수는 배열 크기 - 라운드 횟수 만큼 비교한다.
전체적인 흐름을 보자면 다음과 같은 형태로 정렬 한다.
- Insertion Sort [삽입 정렬]
삽입 정렬은 현재 비교하고자 하는 target(타겟)과 그 이전의 원소들과 비교하며 자리를 교환(swap)하는 정렬 방법이다.
말로만 설명하기에는 어려울 수 있으나 그림으로 보면 이해하기 쉬우니 일단 삽입 정렬에 대한 특징만 짚고 넘어가보자.
삽입 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다.
그리고 이전에 다뤘던 선택 정렬과는 달리 삽입 정렬은 '안정 정렬'이다.
- 정렬 방법
삽입 정렬의 경우 원리 자체는 간단하다. 앞에서부터 해당 원소가 위치 할 곳을 탐색하고 해당 위치에 삽입하는 것이다.
삽입 정렬의 전체적인 과정은 이렇다. (오름차순을 기준으로 설명)
1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫 번째 타겟은 두 번째 원소부터 시작한다.)
2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.
3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.
즉, 그림으로 보면 다음과 같은 과정을 거친다.
첫 번째 원소는 타겟이 되어도 비교 할 원소가 없기 때문에 처음 원소부터 타겟이 될 필요가 없고 두 번째 원소부터 타겟이 되면 된다.
전체적인 흐름을 보자면 다음과 같은 형태로 정렬 한다.
