싸드의 DEVELOPER

선택정렬이란? 선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.주어진 리스트 중에 최솟값을 찾는다.그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.출처 - 위키 출처는 위키가 최고다. 그럼 이제 자바로 구현해보자 public static void main(String[] arg){ int[] arr = {3,1,2,10,3,99, 19};selectionSort(arr);System.out.println(Arrays.toString..

이번엔 가장 빠르다는 퀵퀵소트에 대해 알아보자. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 그리고 퀵 정렬은 정렬을 위해 O(log n)만큼의 memory를 필요로한다. 또한 퀵 정렬은 불안정 정렬에 속한다. 퀵 정렬은 분할 정..

MergeSort란?합병 정렬은 다음과 같이 작동한다.리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.출처 - 위키 뭐 설명은 여기저기서 다 보면 이해 가능할거라 생각한다. 그럼 자바로 한번 구현해보자. public static void main(String[] args) { int[] arr = {3,2,9,5,10,15,40,1,22,2,99}; mergeSort(arr); System.out.println("arr: " + Arrays.toString(arr));} // 배열들을 크..