C 자료구조/Sort Basic
-
List SortC 자료구조/Sort Basic 2020. 9. 15. 19:25
구현 방식에는 두 가지 방법이 있다. 1. 데이터를 리스트에 모두 저장하고 나서 리스트 정렬하는 방식 리스트에서 먼저, 정수값이 들어있는 배열(정렬되지 않은 )을 리스트에 데이터를 다 집어 넣고나서, 해당 리스트에서 정렬을 하는 방법을 만들어 보고자 한다. 정렬을 할 때, 여기서 버블 정렬을 이용했다. 프로그램 실행결과 소스 파일 2. 데이터를 리스트에 저장하면서, 리스트를 정렬하는 방식 배열의 데이터를 리스트에 넣어줄때, 정렬을 하면서 노드 생성하는 것을 만들어 볼 것이다. 두 가지 방식으로 만들어 볼 수 있다. 두 함수들을 차례로 보자. 아래는 나머지 부분이다. AddDataTwo함수의 실행결과 AddDataOne함수의 실행결과 소스 파일
-
Shell SortC 자료구조/Sort Basic 2020. 9. 15. 18:19
참고문헌 삽입정렬의 문제점 삽입정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다. 만약 삽입되어야할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다. 쉘 정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다. 구현 방식 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법이다. Shell정렬은 삽입 정렬보다 빠르다. 삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다. 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다. 쉘정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다. 삽입 정렬과는 다르게 쉘 정렬은 전체의 ..
-
Insertion SortC 자료구조/Sort Basic 2020. 9. 15. 17:58
참고 문헌 삽입 정렬의 장점과 단점 삽입정렬은 연결리스트에서 최적. 그리고 정렬할 데이터들이 얼추 정리가 됬을때, 가장 최적화. 최악은 자료들이 정 반대로 정렬되어있을때 연산량이 많다. 구현 version1 삽입 정렬의 원리는 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써, 정렬이 유지되게 한다. 이와 같은 작업을 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다. [그림 1] 정렬되어 있지 않은 리스트의 첫 번째 숫자가 정렬된 리스트의 어느 위치에 삽입되어야 하는가를 판단한 후, 해당 위치에 이 숫자를 삽입하게 되면 정렬된 리스트의 크기는 하나 커지게 ..
-
Bubble SortC 자료구조/Sort Basic 2020. 9. 14. 19:26
참고 문헌 구현 version1 정렬 방식은 오름 차순으로 한다. 버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이러한 리스트의 비교-교환 과정(스캔)이 한 번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동한다. 이러한 비교-교환 과정은 전체 숫자가 정렬될 때까지 계속 된다. 정렬이 안된 오른쪽 리스트를 한 번 스캔하면, 오른쪽 리스트의 오른쪽 끝에 가장 큰 레코드가 위치하게 되고, 오른쪽 리스트는 추가된 레코드를 포함하여 정렬된 상태가 된다. 이러한 스캔 과정을 정..
-
Select Sort (version2)C 자료구조/Sort Basic 2020. 8. 10. 17:44
1. 설명 정렬의 기준은 오름차순이다. 정렬을 할 배열을 A[n]이라 한다. 배열 A[1...n]에서 가장 큰 원소를 찾아, 이 원소와 배열의 맨 끝자리에 있는 A[n]과 자리를 바꾼다. 그러면 방금 맨 뒷자리로 옮긴 원소, 즉, 가장 큰 원소는 자기 자리를 찾았으므로, 더 이상 신경 안써도 된다. 이 원소는 정렬이 끝났다고 볼 수있으므로, 이제 이 원소를 제외한 나머지 원소들도 같은 작업을 반복하면 된다. 아래는 선택 정렬 알고리즘 의사코드 위의 알고리즘을 풀어서 쓴 의사코드 알고리즘의 입력은 정렬해야할 배열 A[1...n]이다. 위의 알고리즘 식 알파에서 변수last는 정렬할 배열의 맨 마지막 인덱스, 즉, 배열의 크기를 나타낸다. 처음에는 배열의 크기가 n으로 시작하므로, A[1...n]을 정렬 대..
-
Select Sort (version1)C 자료구조/Sort Basic 2020. 8. 10. 17:24
1. 설명 정렬은 오름차순을 기준으로 한다. [그림 1] 위의 그림과 같이 입력 배열에서 최소값을 발견한 다음, 이 최소값을 배열의 첫 번째 요소와 교환. 그 다음에는 첫 번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고, 이를 두 번째 요소와 교환한다. 이 절차를 (숫자 개수 - 1) 만큼 되풀이 하면 전체 숫자들이 정렬된다. [그림 2] 아래의 선택 정렬 알고리즘 의사코드를 보자. 위에서 주의할 것은 i값이 0에서 n-2까지만 변화된다는 점이다. 만약, A[0]부터 A[n-2]까지 정렬이 되었으면 이미 A[n-1]이 가장 큰 값이기 때문에 n-1까지 정렬할 필요가 없다. 2. 구현 프로그램 실행결과 3. 소스 파일