최씨네 블로그

Insertion Sort Insertion sort란 필요한 경우에만 위치를 바꿔 적절한 위치에 원소를 삽입하여 정렬하는 알고리즘입니다. 그런데 이 필요한 경우를 알아내기 위해서는 조건이 필요합니다. 위치를 바꿀 요소의 앞 쪽 요소들이 모두 정렬되어있어야 하는 조건인데요. 그림을 통해 확인하면 다음과 같습니다. 4 3 5 1 2 4 3 5 1 2 3 4 5 1 2 3 4 5 1 2 1 3 4 5 2 1 2 3 4 5 1. 처음 위치해있는 4부터 확인합니다. 앞 쪽 요소가 없으니 건너뜁니다. 2. 다음 수 3을 확인합니다. 그 앞 요소인 4와 비교해 3보다 크니 위치를 바꿉니다. 3. 5를 확인합니다. 이미 1,2 과정에서 정렬이 되어있으므로 4하고만 비교를 합니다. 5가 더 크니 위치를 바꾸지않습니다...

Bubble Sort bubble sort란 배열 정렬 시 바로 옆의 수와 비교하여 자신이 옆의 수 보다 클 경우 위치를 바꾸는 정렬입니다. 선택 정렬과 마찬가지로 비효율적인 정렬 방식인데요. 실제 어떻게 작동하는지 한 사이클만 그림으로 확인해보면 다음과 같습니다. 3 2 5 7 1 2 3 5 7 1 2 3 5 7 1 2 3 5 7 1 2 3 5 1 7 1. 우선 첫 번째 인덱스부터 시작합니다. 첫 번째 인덱스에 있는 숫자 3이 2보다 크므로 서로 위치를 바꿉니다. 2. 그리고 두 번째 인덱스와 세 번째 인덱스를 비교합니다. 두 번째 인덱스에는 1번에서 위치가 바뀌었으므로 3을 5와 비교합니다. 3이 5보다 작으므로 바꾸지 않습니다. 3. 위치 변화와 상관없이 세번째 인덱스와 네 번째 인덱스를 비교합니다..

selection sort란 수를 정렬하는 방식 중 가장 원시적인 정렬 알고리즘으로 가장 작은 수를 찾아낸 다음 앞으로 보내는 방식의 정렬 방법입니다. 정렬방식 중 가장 기본적인 정렬방식입니다. 위 그림에서 보다시피 정렬되지 않은 부분에서 최소값을 찾아 앞으로 보내 차례대로 정렬하는 것입니다. (귀찮아서 손으로 그린건 안비밀) 그렇다면 선택정렬을 하기위해선 몇 번의 연산이 필요할까요? N개의 수가 있다면 처음 최솟값을 구해 정렬하는데 N번, 두번째는 N-1번 세번짼 N-2번 ... 마지막 한번까지 N! 번 연산이 필요합니다 이는 공차가 -1인 등차수열로 n(n+1)/2의 공식을 가집니다. 따라서 시간복잡도는 O(N^2)을 가지게 되고 N의 개수가 많아질수록 효율이 굉장히 떨어지게됩니다 ㅠㅠ 따라서 처리해..