삽입 정렬(insertion sort) 알고리즘 개념 요약 손안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다. 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. 삽입 정렬(insertion sort) 알고리즘의 구체적인 개념 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 즉, 두 번째 자료는 첫 ..

소개 Bubble Sort는 인접한 두 수를 비교하여 큰 수를 뒤로 보내는 간단한 정렬 알고리즘으로 의 시간복잡도를 갖습니다. 다른 정렬 알고리즘에 비해 속도가 상당히 느린 편이지만, 코드가 단순하기 때문에 자주 사용됩니다. 배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자. 1회전 첫 번째 자료 7을 두 번째 자료 4와 비교하여 교환하고, 두 번째의 7과 세 번째의 5를 비교하여 교환하고, 세 번째의 7과 네 번째의 1을 비교하여 교환하고, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 네 번 비교한다. 그리고 가장 큰 자료가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 자료는 비교할 필요가 없다. 2회전 첫 번째의 4을 두 번..

선택 정렬 알고리즘 개념 선택 정렬은 원리가 간단하다 우선 배열 Arr[1......n]에서 가장 큰 원소를 찾아 이 원소와 배열의 끝자리에 있는 A[n]과 자리를 바꾼다. 방금 바뀐 맨 뒷자리 원소, 가장 큰 원소는 자기 자리를 찾았으므로 더 이상 신경 쓰지 않아도 된다. 이제 이원소를 제외한 나머지 원소들도 같은 작업을 반복하면 된다. ex) 1 5 20 4 3 --> 정렬할 배열이 주어진다. 가장 큰수인 20을 찾는다 20을 맨 오른쪽 수와 자리 바꾼다. 1 5 3 4 20 맨 오른쪽 수를 제외한 나머지에서 가장 큰 수를 찾는다. 1 5 3 4 -->5 5를 맨 오른쪽 수와 자리 바꾼다 1 4 3 5 이를 반복한다 선택 정렬의 수행 시간은 모든 경우에 대해서 O(n^2)이다. 소스코드 #includ..