pinevienna blog

삽입 정렬은 선택한 요소를 자신보다 더 앞쪽 정렬된 부분의 알맞은 위치에 삽입하며 정렬해 나간다. 최선의 경우 O(n) / 평균, 최악 O(n^2)의 시간복잡도를 가진다. 1) 정렬이 되지 않은 부분의 가장 첫 번째 요소 selection[i]를 선택하고 2) 앞쪽 정렬된 부분의 알맞은 위치에 삽입한다. 2-1) 정렬된 부분을 한 칸씩 뒤로 밀어내며 이동하고 2-2) selection[i]보다 작은 요소를 만날 때까지 2-3) 혹은 가장 앞에 도달할 때까지 이동하여 삽입한다. 1 2 3 4 5 6 7 8 9 10 11 12 void insertionSort(int[] arr){ for(int i = 1 ; i = 0) && (arr[j] > temp)) { arr[j+1] = arr[j--]; } arr..

선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다. 최선, 평균, 최악 모두 O(N^2)의 시간복잡도를 가진다. 1. 아직 정렬되지 않은 부분에서 가장 작은 요소 selection[i]를 선택 2. selection[i]와 아직 정렬되지 않은 부분의 첫번째 요소를 교환 3. n-1회 반복 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 void selectionSort(int[] list) { int indexMin, temp; for (int i = 0; i

칵테일 셰이커 정렬은 양방향 버블 정렬을 말한다. (=셰이커 정렬, 칵테일 정렬) 버블 정렬의 변형으로, 매 패스마다 리스트의 순서를 바꿔서 정렬한다. 최선 = O(N) / 평균, 최악 = O(N^2)의 시간복잡도를 가진다. 홀수 번째의 패스는 가장 작은 요소가 맨 앞에 오도록 교환하고, 짝수 번째의 패스는 가장 큰 요소가 맨 뒤에 오도록 교환한다. 또는 그 반대!! 첫번째 패스가 완료되면 가장 작은 값이 맨 앞으로 이동하기 때문에 두번째 패스는 맨 앞의 요소를 제외하고 뒤로 이동하며 가장 큰 값을 맨 뒤로 보낸다. 세번째 패스는 양 끝의 두 요소를 제외하고 다시 앞으로 이동하며 가장 작은 값을 맨 앞으로 보낸다. 버블 정렬과 비슷하게, 양 끝 요소를 번갈아 제외시키며 패스를 돈다. 1 2 3 4 5 6..

버블 정렬은 서로 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 정렬 알고리즘이다. 요소의 개수가 n일 때 정렬을 총 n-1회 반복한다. 최선, 평균, 최악의 시간복잡도가 모두 O(N^2)이다. 아래는 요소의 개수가 5개일 때 버블 정렬이다. 5-1, 총 4번의 패스를 반복한다. i와 i+1번째 요소를 비교하여 교환하는 것을 볼 수 있다. 한 패스가 끝나면 가장 큰 값이 맨 뒤로 가기 때문에 맨 끝 요소를 하나씩 제외하며 패스를 돈다. (=맨 뒤 요소는 정렬되었으므로 패스에서 제외) 1 2 3 4 5 6 7 8 9 10 11 12 void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i

에라토스테네스의 체는 대표적인 소수 판별 알고리즘이다. 소수는 1과 자기 자신을 제외하고는 약수를 가질 수 없다는 점을 이용한 것으로, 소수의 배수들을 체로 거르듯 모두 지우면 범위 내의 소수를 쉽게 구할 수 있다. 위는 2~120 사이의 소수를 에라토스테네스의 체 알고리즘을 사용하여 찾는 사진이다. 자신의 배수에 해당하는 수들을 모두 제외시키면 된다. (자기자신은 제외) 배수를 찾아 걸러내는 형식이므로 2~n 사이의 소수를 찾는다면 n의 제곱근까지만 계산해주면 된다. 일반적인 소수 찾기 알고리즘의 시간복잡도는 O(N)이지만 에라토스테네스의 체의 시간복잡도는 O(n*log(log n))으로 더 효율적이다. (특정 숫자에 대한 소수 판별에는 더 비효율적이고, 대량의 숫자들을 판별할 때 적합함) 자세한 코드..