지난 학기들의 기록/알고리즘28 [C 알고리즘] 퀵 정렬 - Quick Sort Algorithm 퀵 정렬은 이름부터 퀵 정렬이다. 당연히 앞의 3개 정렬이 가지는 시간복잡도 O(N^2)보다는 빠를 것이다. 퀵 정렬은 대표적인 분할정복 알고리즘으로 O(N*logN)의 시간복잡도를 가진다. 퀵 정렬은 피벗값(=키값)이라는 개념이 등장하게 되는데 이것을 먼저 받아들여야한다. 보통 피벗값은 가장 앞에있는 값을 일반적으로 선택한다. 피벗값을 선택 한 후에 , 왼쪽에서 피벗값보다 큰 값을 선택하고, 오른쪽에서 작은 값을 선택한다. 예시를 통해 나타내자면 3 7 8 1 5 9 6 10 2 4 // 피벗값 : 3 , 왼쪽에서 선택한 큰 값 : 7 , 오른쪽에서 선택한 작은 값 2 이게 일반적인 반복상황이다. 이런 경우에 7과 2를 바꾸어준다. 이런 과정을 언제까지 반복하냐면 엇갈릴때까지 반복한다. 여기서 말하는 .. 2020. 5. 12. [C 알고리즘] 삽입정렬 - Insertion Sort Algorithm 삽입정렬이 앞서 배운 선택정렬, 버블정렬과 차이점을 가지는게 있다면 그것은 '필요할때만'이라는 키워드다. 삽입정렬의 핵심은 각 숫자를 적절한 위치에 삽입하는 것인데, 여기서 필요할때만 위치를 바꾼다는 점 때문에 앞의 두 정렬보다는 속도가 빠르다. 하지만 여전히 O(N^2)의 속도로 느린 정렬 알고리즘에 속한다. 삽입정렬 알고리즘 떠올리기 앞의 숫자가 더 작다면 그 앞은 이미 정렬되어있는것이다. 앞의 숫자가 작을때까지 반복해야한다. 인덱스를 1씩 늘리며 각 인덱스마다 시행하며 그 시행에선 WHILE문을 시행한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 4.. 2020. 5. 12. [C 알고리즘] 버블 정렬- Bubble Sort Algorithm 앞서 배운 선택정렬은 제일 최솟값을 선택하여 앞으로 보내주는 과정을 반복하는것이었다. 이번에 배울 버블정렬의 핵심 아이디어는 옆에 있는 수와 비교해서 작은것을 앞으로 보내는 것이다. 1 10 5 8 7 6 4 3 2 9 1 10 5 8 7 6 4 3 2 9 1 5 10 8 7 6 4 3 2 9 1 5 8 10 7 6 4 3 2 9 1 5 8 7 10 6 4 3 2 9 위 과정을 반복하게 되면 1 5 8 7 6 4 3 2 9 10 이 된다. 즉 한번의 싸이클로 시행하게되면 가장 큰수가 제일 뒤로 밀려나는 꼴이다. 이 같은 과정을 N번 반복해주므로 빅오표기법에 의한 시간복잡도는 O(N^2)이다. 1. N번 반복해주는 A라는 알고리즘정렬 2. A는 첫번째 인덱스부터 시작하여 그 옆의 인덱스와 대소관계를 비교하.. 2020. 5. 11. [C 알고리즘] 선택정렬 - Selection Sort Algorithm 가장 기초적인 정렬 4가지, 선택정렬 버블정렬 삽입정렬 퀵정렬을 배워볼것이다. 먼저 선택정렬이다 선택정렬의 핵심아이디어는 말그대로 '선택' 이다. 최솟값을 찾아 선택하여 제일 앞으로 보내자. 예시를 통해 이해해보자 1 10 5 8 7 6 4 3 2 9 와 같은 10개의 정수가 있을때. 제일 작은 원소는 1이다. 이미 제일 앞에 와있다. 그 다음 1을 고정시킨후 제일 작은 원소를 선택해보자 2이다. 1 10 5 8 7 6 4 3 2 9 1 2 10 5 8 7 6 4 3 9 1 2 3 10 5 8 7 6 4 9 위 와같은 과정을 반복함으로써 정렬되는 것이다. 1.먼저 작은 값을 선택한다 . MIN 값 찾기 2. 그리고 고정된 숫자제외 제일 앞으로 보내준다. (= i번째 인덱스의 값과 교환한다.) 1 2 3 .. 2020. 5. 11. 이전 1 ··· 4 5 6 7 다음
