본문 바로가기

정렬

 (5)
정렬 알고리즘5 - 퀵정렬(Quick Sort) 퀵정렬(Quick Sort) 작동방식 정렬할 피봇(기준값)을 정하고, 피봇을 기준으로 크기가 큰 그룹과 작은 그룹으로 나눈다. 나뉜 각 그룹에서 다시 피봇을 정하고, 피봇 기준으로 크기가 큰 그룹과 작은 그룹으로 나눈다. 그룹을 더이상 나눌 수 없을때까지 위 과정을 반복한다. 특징 명칭에서 알 수 있듯이 빠른 정렬 방법이다 분할 정복 알고리즘의 한 기법 퀵 정렬은 부분교환 정렬(Partition Exchange Sort)이라고도 불림. 요소간 비교하는 방식으로 정렬되는 방식 그룹 나누는 함수를 재호출 하는 즉, 재귀적으로 호출하는 방식이다. 임의의 피봇(기준값을 정한다. 꽤 빠른 정렬 방법에 해당한다. 그룹에서 어떤 요소를 피봇으로 정하는지에 따라 정렬의 성능이 결정된다. 데이터를 나열한 순서가 좋지 않..
정렬 알고리즘4 - 셸 정렬(Shell Sort) 셸 정렬(Shell Sort) 작동방식 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 삽입정렬을 실시한 뒤 그룹을 합치면서 정렬을 반복하면서 요소의 이동횟수를 줄이는 방법 특징 삽입정렬의 단점은 보완하고 장점은 살린 정렬 방법 (삽입정렬의 단점은 삽입할 위치가 멀리 떨어진 경우 요소를 이동시키는 거리가 길다는 것이다. 삽입정렬의 장점은 정렬된 상태에 가까워질수록 정렬시키는 속도가 더욱 빨라진다는 것이다) 셸정렬은 그룹별로 미리 몇차례 정렬을 해둔뒤에 삽입정렬을 실시해 삽입정렬의 장점을 취하는 정렬방법이다. 셸정렬을 실시하면 정렬해야하는 횟수는 증가하지만 요소이동 횟수가 줄어들어 보다 효율적인 정렬이 가능하다. 정렬되는 모습 살펴보기 정렬할 요소는 [6, 2, 5, 3, 1, 7, 4, 8], 이렇게 숫..
정렬 알고리즘3 - 삽입정렬(Insertion Sort) 삽입정렬(Insertion Sort) 작동방식 정렬된 데이터 중에 적절한 위치를 찾아 새로운 값을 넣어주는(삽입) 방식 특징 앞에서부터 차례대로 정렬된다 구현이 간단하다 방식이 단순하고 효율적이다. 버블정렬, 선택정렬 보다 효율이 좋다. 요소가 많을수록 효율이 떨어진다. 실시간 정렬이 가능하다. 정렬할 항목이 계속 추가되더라도 적절한 위치를 찾아 삽입하면 되기 때문. 어느 정도 정렬되어 있는 것을 완전히 정렬하는데 적합한 방식 반대로 역순으로 된 상태를 재정렬하는 경우 약하다 새로 삽입되는 값이 앞쪽에 위치할수록 한칸씩 밀리는 배열값 개수가 많아지기 때문이다. [ 2, 17, 8, 3, 15, 9, 4, 6, 13, 7, 1, 5, 11 ] 와 같은 숫자집합이 있을때 아래와 같은 순서로 정렬된다. 정렬된..
정렬 알고리즘2 - 선택정렬(Selection Sort) 선택정렬 (Selection Sort) 작동방식 정렬해야 하는 값에서 임시최솟값[최댓값]을 정한다(보통 첫번째 값을 할당함) 반복문을 돌면서 정렬되지 않은 값과 비교하면서 진짜 최솟값[최댓값]을 찾는다 진짜최솟값의 위치가 파악되면 임시최솟값의 위치와 맞바꾼다 (반복) 정렬한 값을 제외하고 다시 최솟값[최댓값]의 위치를 찾는다 특징 정렬해야 하는 값 중에서 다음 최솟값[최댓값]을 찾아 정렬하는 방식 좌측[우측]부터 순서대로 정렬된다 버블정렬과 마찬가지로 n제곱만큼 수행된다 버블정렬에 비해 요소간 자리이동하는 작업이 적기 때문에 실제효율은 버블정렬보다 좋다 예시 [ 1, 14, 9, 6, 2, 19, 4, 7 ] 와 같은 숫자집합이 있을때 아래와 같은 순서로 정렬된다. 1 2 9 6 14 19 4 7 1 2..

티스토리툴바