선택 정렬, 삽입 정렬, 퀵 정렬하는 과정에 대하여 단계별로 정확히 쓰시오.

소개

다음의 자료들에 대하여 선택 정렬, 삽입 정렬, 퀵 정렬하는 과정에 대하여 단계별로 정확히 쓰시오.

목차

1. 선택 정렬(selection sort)
2. 삽입 정렬(insertion sort)
3. 퀵 정렬(Quick Sort)
4. 참고자료 및 문헌.

본문내용

1. 선택 정렬(selection sort)
선택 정렬(selection sort)은 매번 최소값을 선택하여 교환하는 과정을 통해 오름차순으로 정렬하는 알고리즘이다.

전체의 최소값을 선택하여 배열의 0번 원소와 자리를 바꾼 다음에 0번 원소를 제외한 다른 원소에서 최소값을 선택하여, 배열의 1번 원소와 자리를 바꾼다. 이런 방식으로 마지막 2개의 원소 중 최소값을 선택하여 자리를 바꿈으로 오름차순의 정렬을 마친다.

n개의 레코드 중에서 첫 번째 값을 키로 하여 나머지 데이터 중에서 최소값을 선택하여 비교한 후, 선택된 값이 키 값보다 작으면 서로 교환하고 그렇지 않다면 다음 값을 키로 하여 (n-1)번 만큼 수행하는 정렬이다. 레코드의 수가 n일 때, 비교 횟수는
이며 시간 복잡도는 O()이다. 레코드가 어떤 순서로 정렬되어 있든지 간에
즉, 최악 시간복잡도, 최선 시간복잡도, 평균 시간복잡도 모두 O()로 동일하다.

[선택 정렬 알고리즘]
①n=레코드 수
②첫 번째의 값을 기준으로 정한다.
③처음부터 끝까지의 키 값과 비교하여 키보다 작으면 서로 위치를 변경한다.
④키=키+1
⑤n번 비교 되었으면 종료, 그렇지 않다면 ③으로 돌아간다.

<중 략>

2. 삽입 정렬(insertion sort)
삽입 정렬(insertion sort)은 배열이 정렬된 부분(앞부분)과 정렬 안 된 부분 (뒷부분)으로 나눈 뒤 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입해 정렬되도록 하는 과정을 반복하는 알고리즘이다.

정렬 안 된 부분의 숫자 하나가 정렬된 부분에 삽입 정렬된 부분의 원소 수가 1개 늘어나고 ,동시에 정렬이 안 된 부분의 원소 수는 1개 줄어든다. 반복하여 수행하면 마지막에는 정렬이 안 된 부분 외에 아무 원소도 남지않는다. 단, 정렬은 배열의 첫 번째 원소만이 정렬된 부분에 있는 상태에서 정렬을 시작한다.

참고자료

· https://hsp1116.tistory.com/33
· https://velog.io/@wan088/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC
· https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC
· https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC
· https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC
· https://ratsgo.github.io/data%20structure&algorithm/2017/09/06/insmersort/