SW 꿈나무

Quick Sort (퀵 정렬) 분할 정복 알고리즘으로 인덱스를 분할(Devide) 후, 정복(Conquer)과 결합(Combine)하는 정렬 피벗을 정한 후, 피벗과의 대소비교로 좌, 우를 정렬하고 각 좌, 우 정렬에 대해서도 반복하는 정렬 장점 : 빠르다. 평균적으로 Merge Sort 보다 빠르다. 단점 : 피벗 선택에 따라 시간복잡도가 바뀔 수 있다. 같은 수를 비교할 경우, 위치 이동이 일어날 수 있다. 시간복잡도 : Best T(n) = n log_2 n Worst T(n) = n^2 동작 순서 피벗을 선택한다. 피벗과 각 인덱스 대소비교 후, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시킨다. 피벗을 제 위치로 이동시킨다. 나눈 배열의 사이즈가 1이 될 때까지 피벗 좌, 우 측 배열에..

Merge Sort (합병 정렬) 분할 정복 알고리즘으로 인덱스를 분할(Devide) 후, 정복(Conquer)과 결합(Combine)하는 정렬 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아 원래 문제를 해결하는 방법 장점 : 안정적인 정렬 방법. 데이터 분포에 구애받지 않고 정렬되는 시간이 동일하다. ​ 레코드를 연결 리스트로 구성하면 링크 인덱스만 변경되어 데이터 이동을 무시할 수 있을 정도로 작아진다. 단점 : 레코드를 배열로 구성할 경우, 임시 배열이 필요하다. 시간복잡도 : T(n) = n log_2 n 동작 순서 모든 배열을 하나의 배열로 나눌 때까지 배열을 같은 크기의 2개의 부분 배열로 분할한다. 나눠진 배열들을 역순으로 크기를 비교하며 정렬한다. Code #incl..

Bubble Sort (거품 정렬) 인접한 두 인덱스를 비교하여 위치를 교환해가며 정렬하는 방식. 코드가 단순하다. 연산 횟수가 많아 데이터 수가 많아질수록 성능이 저하된다. 시간복잡도 : T(n) = n(n-1)/2 = O(n^2) 동작 순서 (최소 선택 정렬을 예시로 함.) 첫번째 인덱스부터 인접한 2개의 인덱스를 비교하여 순서가 맞지 않으면 위치를 교환한다. 가장 큰 값이 마지막 인덱스에 위치하므로, 배열의 크기 N - 시행순서 n 까지 반복한다. Code #include #define ARRAY_SIZE 10 //Logic 부-------------------------------------------- void bubble_sort (int array[], int n) { int temp=0; ..

Insertion Sort (삽입 정렬) 자신과 앞의 원소의 크기를 비교하여 자신의 위치에 삽입하는 정렬 방식 장점 : 인덱스 수가 적을 경우나 대부분 정렬되어 있을 경우 효율적이다. 단점 : 비교적 많은 인덱스의 이동으로 인덱스 수가 많은 경우 비효율적이다. 시간복잡도 : Best T(n) = n-1 = O(n) Worst T(n) = n(n-1)/2 + 2(n-1) = O(n^2) 동작 순서 (최소 선택 정렬을 예시로 함.) 두 번째 인덱스부터 앞쪽 자료와 크기를 비교한다. 자신의 위치에 삽입 한다. 세 번째 인덱스부터 위 정렬을 반복한다. 반복. Code #include // 헤더파일 선언 #define ARRAY_SIZE 10 // ARRAY SIZE 10으로 정의 // Logic 부-------..

Selection Sort (선택 정렬) 전체 자료 중, 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식 입력 배열 외 추가 메모리를 요구하지 않음. 장점 : 자료 이동 횟수가 사전에 정해진다. 단점 : 값이 같은 경우에도 위치가 변경되므로 안정성을 만족하지 않는다. -> Code에서 극복하는 부분 참조 시간복잡도 : T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2) 동작 순서 (최소 선택 정렬을 예시로 함.) 첫 번째 인덱스부터 마지막까지 크기를 비교하여 제일 작은 값을 찾는다. 현재 인덱스와 제일 작은 값의 위치를 바꾼다. 두 번째 인덱스부터 위 정렬을 반복한다. 반복. Code #include // 헤더파일 선언 #define ARRAY_SI..