이번에는 삽입정렬입니다!
선택정렬의 경우 앞서나온 선택정렬과 버블정렬에 비해 더욱 효율적인 알고리즘이라 할 수 있습니다.
그 이유는 숫자를 대소비교하여 숫자를 앞으로 보내주는 선택정렬과 바로옆에 있는 모든값을 비교하는 버블정렬과 비교하는 경우와 달리, 위치를 저장할 수 있다는 것에서 차이점이 생깁니다!
예제는 계속해서 1/7/3/5/8/6/9/2/4에 대해 정렬을 하는 예제입니다!
#include <iostream> using namespace std; int main() { int temp; int array[9] = { 1, 7, 3, 5, 8, 6, 9, 2, 4 }; for (int i = 0; i < 8; i++) { int j = i; while (array[j] > array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; j--; } } for (int i = 0; i < 9; i++) { cout << array[i] << " "; } return 0; }
💡 이제 코드를 하나하나 뜯어 봅시다!
첫 번째 i for문을 보게되면 i를 0부터 8미만(정수형이니 7)까지 8번 증가시킵니다! 버블정렬과 선택정렬은 총 9번의 반복을 수행하던것과 비교하게 되면 한번의 횟수가 적은데 그 이유는 바로 배열의 첫 번째 요소를 이미 정렬이 완료된 것으로 간주하기 때문입니다!
다음을 보면 for문안에서 j를 따로 변수로 선언하여 i값을 넣어줍니다! 사실 이 과정이 필요한가? 라는 생각이 들 수 있을것이라 생각합니다. 근데 만약 j라는 변수를 따로 선언하는 과정을 생략하게 된다면 (j--;이 부분) 무한루프에 빠져 for문을 빠져나오지 못하는 상황이 발생할 수 있어 j를 따로 선언하는 과정을 거쳐야 합니다.
for (int i = 0; i < 8; i++) // 입력된 배열은 이미 정렬이 되어있다는 가정으로 인해 i는 8까지만 증가시켜줍니다.
int j = i; // 무한루프에 빠지지 않게 하기위해 j를 따로 선언합니다.
삽입정렬은 선택정렬과 버블정렬보다 더욱 빠른 시간복잡도를 갖고있지는 않습니다. 최악의 경우가 발생하였을 때에는 똑같이 O(N^2)의 반복횟수를 수행하기 때문입니다. 하지만 이는 처음 주어진 조건이 최악의 조건일때에만 해당되며 만약 배열이 거의 끝난 경우에서는 앞서 배운 정렬들에 비해 훨씬 빠른 연산을 수행할 수 있게되며, 이러한 이유로 보다 효율적인 알고리즘이라 할 수 있습니다.
점점 효율적이고 쓸모있는 알고리즘을 배우고 있는거 같네요..!
