코딩하는 털보

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC 퀵 정렬은 병합 정렬과 동일하게 분할 정복을 사용하여 정렬 문제를 해결한다. 퀵 정렬의 특별한 점은 pivot이라는 개념을 사용하는데, 배열 요소 중 하나를 pivot으로 정하여 pivot보다 작은 값을 왼쪽으로 큰 값을 오른쪽으로 배치하고 분할된 두 영역에 다시 위 과정을 크기가 1이 될 때 까지 반복하여 마지막에 모두 합치면 정렬되는 방식이다. 퀵 정렬의 시간복잡도는 O(nlogn)이다. Big O notation은 알다시피 가장 최악의 상황에서의 시간복잡도를 표현하는데, 퀵정렬의 최악의 시나리오에서 시간복잡도는 O(n^2)이다. 하지만 퀵 정렬은 특별하게 pivot을 어떤 요소로 선택하느냐에 따..

합병 정렬은 분할 정복 알고리즘을 이용한 정렬 방법이다. 분할 정복은 큰 문제를 작은 문제로 쪼개어 작은 단위의 문제를 먼저 해결하면서 병합시켜 마지막으로 가장 큰 문제를 해결하는 문제 풀이 방법이다. 합병 정렬의 과정은 크게 배열을 분할하는 부분과 분할된 배열을 다시 합병하는 부분으로 나뉘어 진다. 분할에서는 배열을 두 개의 배열로 분할한다. 합병에서는 두 배열을 정렬을 하면서 합친다. 시간복잡도는 분할에서 log2(N), 합병에서 N으로 분할이되는 만큼 다시 합병하기 때문에 둘을 곱하여 N*log2(N)이 된다. 성능이 선택, 버블, 삽입 정렬과 비교하여 효율적이고 안정적이기 때문에 자주 사용되는 정렬 방법 중 하나이다. Java의 Arrays.sort() 및 Python sorted() 또한 합병 ..

버블 정렬은 배열에서 차례대로 두 개의 붙어있는 인덱스를 비교하여 더 큰 값을 뒤로 보내는 정렬 방법이다. 가장 큰 값이 먼저 맨 뒤로 보내지고 그 다음 뒤에서부터 순차적으로 정렬이 완성된다. n = array length 처음엔 인덱스 0부터 n-2까지 그다음 인덱스와 비교하면서 다음 인덱스가 크면 서로 교환 위 절차를 0~n-3, 0~n-4, 0~n-5, ... 0~0으로 총 n-1번 순회 i : 0~n-2 j : 0~n-2-i 최선의 경우, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 성능이 좋지 못하여 구현이 쉽다는 장점 말고는 다른 정렬 방법과 비교했을 때 좋은 정렬 방법이 아님.

배열이나 리스트의 원소를 하나씩 비교하면서 알맞은 위치에 삽입하여 정렬하는 방법 쉽게 생각하면 배열 앞부분부터 정렬을 시작하고 모든 배열이 정렬될 때 까지 하나씩 정렬 영역에 알맞는 위치에 삽입하는 정렬 방법이다. 선택 정렬과 마찬가지로 O(n^2)의 비효율적인 시간 복잡도를 가지게 된다. 정렬을 하는 방법인데 정렬이 안되어있을수록 성능이 떨어지게 된다. 정렬이 어느정도 잘 되어있다는 보장이 있다면 좋을 수 있지만 그렇지 않다면 다른 정렬 방법이 선호된다.

선택 정렬은 배열의 부분 배열에서 최소값(또는 최대값)을 찾아 부분 배열의 시작 인덱스와 값을 교환하는 정렬 방법이다. 선택 정렬 알고리즘의 구체적인 과정은 다음과 같다. 배열의 첫 번째 원소를 선택 이후 원소들 중에서 최소값 검색 최소값을 찾았다면, 해당 최소값을 현재 선택한 원소와 교환 배열의 다음 원소를 선택하여 위 과정을 반복 모든 원소에 대해 위 과정을 반복하여 정렬을 완료 코드만 봐도 알수 있듯이 이 정렬법의 시간 복잡도는 O(n^2)이다. 배열의 크기가 클수록 성능이 좋지 못하므로 일반적으로는 이보다 더 효율적인 정렬 알고리즘을 사용하게 된다.