정렬알고리즘

참고사이트 : https://www.youtube.com/watch?v=ww6URL1l1ho

이진정렬
버블정렬
삽입정렬
병합
퀵소트

정렬알고리즘은 특정원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 정렬하는 알고리즘이다
정렬알고리즘이 중요한 이유는컴퓨터분야에서 중요시되는 문제중하나이고, 탐색에 중요하기 때문이다.(43억개 중 특정값을 찾아야 할 경우 32회만으로도 탐색이 가능하다) 또한 프로그래밍과 알고리즘 이해에 많은 도움이 된다.(프로그래밍 기초문법, 분할정복 알고리즘, 자료구조, 시간복잡도)
정렬알고리즘의 종류에는 버블정렬, 삽입정렬, 병합정렬, 퀵정렬이 있다
버블 정렬은 가장 기초적인 알고리즘이다. 인접한 두개의 요소를 비교해가면서 정렬을 진행하는 방식이다. 한번 돌때마다 마지막 요소가 정렬되는것이 거품이 올라오는 것 처럼 보여서 버블정렬이라고 부른다고한다.

버블정렬의 특징은 구현이 매우 간단하다는것이다. 단점은 순서에 맞지않는 요소들의 교환이 자주 일어난다.
시간복잡도는 최악은 O(n^2), 평균은 O(n^2), 최선은 O(n)이다.

다음으로는 선택정렬에 대해 설명하겠다.
선택정렬은 가장 기초적인 알고리즘이다
전체 범위에서 차례대로 가장 작은 숫자를 탐색하고, 가장 왼쪽에서부터 차례대로 교환하는 방식이다.
전체 범위를 돌며 작은 숫자를 선택하여 정렬하는것이므로 선택정렬이라고 한다.

선택정렬의 장점은 자료 이동횟수가 미리 결정된다는것이다. 하지만 같은 값이 있을경우에는 상대적인 위치가 변경될 수 있다는 단점이 있다.
시간복잡도는 최악, 평균, 최선 모두 O(n^2)이다.

다음은 삽입정렬이다. 삽입정렬 또한 가장 기초적인 알고리즘이다. 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식이다. 이미 정렬된 배열에서 자기 자신을 찾아 삽입된다고 하여 삽입정렬이라고 한다.

이렇게 정렬되지 않은 요소가 이미 정렬된 배열부분과 비교하여 자신의 위치를 찾아가는 알고리즘이다.

삽입정렬의 장점은 최선의 경우 O(n)이 나온다는점이다. 요소가 너무 많으면 비교적 많은 이동을 해야하므로 성능이 좋지않다는 단점이 있다.
시간복잡도는 최악 : O(n^2), 평균 : O(n^2), 최선 : O(n)이다.

다음으로 병합정렬은 복잡하지만 효율적인 알고리즘이라고 할 수 있다. '분할정복'이라는 알고리즘 디자인 기법에 근거하여 복잡한 문제를 복잡하지않은 문제로 '분할'하여 '정복'하는 방식이다. 병합정렬은 분할보다는 병합과정에서 이루어지기때문에 병합정렬이라고 이름지어졌다.

병합정렬은 데이터 분포의 영향을 덜 받는다는 장점이 있지만, 요소를 배열로 구성하면, 임시배열이 필요하다는 단점이 있다.
시간복잡도는 최악, 평균, 최선 모두 O(nlogn)이다.

퀵정렬은 복잡하지만 효율적인 알고리즘이다. 특정요소를 기준점(pivot)으로 잡고, 기준점보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 두고 왼쪽과 오른쪽을 각각 정복하는 방식이다.
다른 알고리즘보다 효율적이고 빨라서 퀵 정복이라고 한다.

퀵정렬은 다른 알고리즘보다 평균 실행시간이 빠르다는 장점이 있지만 pivot에 따라서 성능차이가 심하다는 단점이 있다.
퀵정렬의 시간복잡도는 pivot이 중간에 가까운 값을 찾을수록 성능이 좋다.
최악은 O(n^2), 평균은 O(nlogn), 최선은 O(nlogn)이다.

정렬알고리즘 선택시 고려사항으로는 시간복잡도가 전부는 아니므로 알고리즘의 장단점에 따라 상황에 따라 선택해야한다는 점이다.
버블, 삽입, 병합 정렬에는 안정성이 존재하지만 선택, 퀵, 힙 정렬에는 안정성이 존재하지않는다.
그 외에도 공간복잡도, 지역성, 키값들의 분포상태, 데이터의 양, 초기 데이터의 배열상태, 사용 컴퓨터 시스템의 특성이 있다.