공부하는 스누피

선택 정렬 - 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복한다. - 시간복잡도는 O(N^2)이다. => 배열 순회하는 반복문(N) + 가장 작은 데이터를 찾는 반복문(N-1+N-2+...+2) = N * (N+1) / 2 1) 바꿀 데이터의 인덱스를 i라 하고, 0(맨 앞)으로 초기화한다. 2) 가장 작은 데이터를 선택해 i 인덱스의 데이터와 바꾼다. 3) 그다음 작은 데이터를 선택해 i+1 인덱스에 있는 데이터와 바꾼다. 4) i가 배열의 마지막에 도착할 때까지 반복한다. def selection(arr): for i in range(len(arr)): min_index = i for j in range(i+1, len(arr)): if arr[i] > arr[j]: min_index = j..

퀵 정렬이란? Quick sort는 Divide and Conquer 알고리즘으로, 평균적으로 매우 빠른 수행 속도를 보여준다. 시간복잡도가 O(NlogN)으로 Merge sort와 동일하지만, 배열을 균등하지 않게 분할하고 추가적인 메모리 공간을 필요로 하지 않는다. 빠르고 메모리도 덜 차지하지만 pivot을 잘못 설정했을 경우, 최악의 경우에는 시간복잡도가 O(N^2)으로 다른 비효율적인 정렬 알고리즘보다 나은 것이 없다. 그래서 pivot의 위치에 큰 영향을 받지 않는 배열에 적합하다. pivot은 배열을 분할하는 기준점으로, pivot으로 나눠진 두 배열의 원소를 순서대로 꺼내 비교하면서 정렬한다. 원리 배열을 정렬하려면 먼저 3가지 변수를 설정해 두어야 한다. left: 배열 맨 왼쪽 인덱스. ..