최근 정렬알고리즘을 공부한 것을 바탕으로 문제를 풀어보았습니다. 최대한 매서드를 사용하지 않고 정렬 알고리즘을 사용해 풀어보았습니다. 1. 문제설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결..
정렬알고리즘
힙 정렬 내림차순을 기준으로 정렬. 완전 이진 트리의 일종으로 우선 순위 큐를 위하여 만들어진 자료구조. 최댓값, 최솟값을 쉽게 추출할 수 있는 구조. 내림차순 정렬을 위해서는 최대 힙을 구성, 오름차순 정렬을 위해서는 최소 힙을 구성하면 됨. 배열을 최대 힙으로 만듦(내림차순 정렬). 배열의 뒤부터 하나씩 저장. 삭제되는 원소들을 순서대로 정렬(오름차순 정렬). 힙 정렬 C# 코드 public void Heap_Sort(List list) { for (int i = (list .Count- 1)/2; i >= 0; i++) { My_Heap(list, i, list.Count); } for (int i = list.Count - 1; i > 0; i++) { int temp = list[0]; list..
병합 정렬 오름차순을 기준으로 정렬. 비교적 안정 정렬에 속하며, 분할 정복 알고리즘 중 하나. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봄. 정렬되지 않은 리스트를 낱개가 될 때까지 절반씩 반복적으로 두 부분 리스트로 나눔. 재귀함수를 통해 병합 정렬을 진행. 병합 정렬 C# 코드 public List DivideArr(List list) { if (list.Count leftIndex && rightList.Count > rightIndex) { if (leftList[leftIndex] leftIndex) { for (int i = leftIndex; i < leftList.Count; i++) { mergedList.Add(leftList[i]); } } else if (rightLis..
셸 정렬 오름차순을 기준으로 정렬. 삽입정렬을 보완한 알고리즘. 배열을 일정한 기준의 간격으로 분류(부분 리스트를 생성). 부분 리스트에서 삽입정렬을 수행. 이 과정을 간격이 1일때까지 반복 수행. 셸 정렬 C# 코드 public void Shell_Sort(int[] array) { //1.매개변수 배열의 크기의 절반만큼 갭을 만든다. int gap; for (int i = array.Length / 2; i > 0; i = i / 2) { gap = i; //갭이 짝수면 갭+1. ex)배열크기=11. 갭=5,3,1 if (gap % 2 == 0) { gap++; } for (int k = 0; k < gap; k++) { Shell_Insert_Sort(array, k, gap); } } } publ..
퀵 정렬 오름차순을 기준으로 정렬. 불안정 정렬에 속함. 매우 빠른 수행 속도를 자랑하는 방법. 기준이 되는 원소(Pivot)을 잡고 해당 원소보다 작은 값을 왼쪽, 큰 값을 오른쪽에 배치해주며 정렬하는 방법. 퀵 정렬 C# 코드 void SortQuick(int[] _arr, int _first, int _last) { if (_first < _last) { int pivot = GetPivot(_arr, _first, _last); SortQuick(_arr, _first, pivot - 1); SortQuick(_arr, pivot + 1, _last); } } int GetPivot(int[] _arr, int _first, int _last) { int pivot = _arr[_first]; i..
삽입 정렬 오름차순을 기준으로 정렬. 배열의 모든 원소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 해당 원소의 위치를 찾아 삽입하는 정렬. 삽입 정렬 C# 코드 public void Insert_Sort(int[] array) { int temp; for (int i = 1; i 0; k--) { if (array[k] < array[k - 1]) { temp = array[k]; array[k] = array[k - 1]; array[k - 1] = temp; } } } } 장점 - 비교적 안정한 정렬 방법. - 배열 원소의 수가 적을 경우 유리한 방법. - 대부분의 원소가 이미 정렬되어 있는 경우 매우 효율적임..
선택 정렬 오름차순을 기준으로 정렬. 배열의 최소값을 찾고, 그 값을 맨 앞에 위치한 원소와 교체. 맨 처음 위치를 뺀 나머지 원소들도 같은 방법으로 교체. 선택 정렬 C# 코드 public void Select_Sort(List _list) { int indexMin; int temp; for (int i = 0; i < _list.Count - 1; i++) { indexMin = i; for (int k = i + 1; k < _list.Count; k++) { if (_list[k] < _list[indexMin]) { indexMin = k; } } temp = _list[i]; _list[i] = _list[indexMin]; _list[indexMin] = temp; } 장점 - 자료 이동 ..
버블 정렬 오름차순을 기준으로 정렬. 서로 인접한 두 원소를 검사하여 정렬. 인접한 2개의 원소를 비교하여 크기 순으로 자리를 재배치. 버블 정렬 C# 코드 public void Bubble_Sort(int[] _list) { int temp; for (int i = _list.Length - 1; i > 0; i--) { for (int k = 0; k _list[k + 1]) { temp = _list[k]; _list[k] = _list[k + 1]; _list[k + 1] = temp; } } } } 장점 - 구현이 간단함. 단점 - 인접한 2개의 원소를 반복적으로 계속 교환해주기 때문에 원소의 수가 많아질수록 시간복잡도가 오래걸림.
