Sorting

Huisu·2023년 4월 22일
Count SortInsertion SortQuick Sortalgorithmsorting
0

Algorithm

목록 보기
4/8
post-thumbnail

Sorting

Sorting

  • 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
  • 비교 가능한 요소들끼리 정렬
  • ascending: 오름차순
  • dscending: 내림차순
  • 비교 대상들끼리는 비교 가능하고 unique해야 함

Selection Sorting

  • 데이터를 정렬된 부분과 정렬되지 않은 부분으로 나눔
  • 정렬되지 않은 부분에서 가장 작은 데이터를 선택해 맨 앞 데이터와 바꾸는 작업 반복
  • n 개의 요소가 있을 때 (n*(n-1))/2 만큼 비교
  • 계산복잡도는 O(n^2)
  • C++ Implementation
    template<class ItemType>
int minIndex(ItemType values[], int start, int end)
{
	int indexOfMin = start;
	for (int index = start + 1; index <= end; index++)
	{
		if (values[index] < values[indexOfMin])
			indexOfMin = index;
	}
	return indexOfMin
}

template<class ItemType>
void SelectionSort(ItemType values[], int numValues)
{
	int endIndex = numValues - 1;
	for (int current = 0; current < endIndex; current++)
	{
		Swap(values[current], values[minIndex(values, current, endIndex)]);
	}
}
  • Python Implementation
    def selection_sort(array):
    for i in range(len(array)):
        min_index = i
        for j in range(i + 1, len(array)):
            if array[min_index] > array[j]:
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]
    return array

Insertion Sort

  • 구조를 만들 때부터 정렬된 상태로 생성하는 방법
  • 특정한 데이터를 적정한 위치에 삽입
  • 끝부터 시작해서 삽입하는 새로운 요소의 위치를 찾을 때까지 공간을 하나씩 밀어내는 방법
  • 요소 하나에 n번씩 비교
  • 계산복잡도는 O(n^2) https://runestone.academy/ns/books/published/pythonds/_images/insertionpass.png
  • C++ Implementation
    template<class ItemType>
void InsertItem(ItemType values[], int start, int end)
{
	bool finished = false;
	int current = end;
	bool moreToSearch = (current != start);

	while (moreToSearch && !finished)
	{
		if (values[current] < values[current - 1])
		{
			Swap(values[current], values[current - 1]);
			current--;
			moreToSearch = (current != start);
		}
		else
			finished = true;
	}
}

template<class ItemType>
void InsertionSort(ItemType values[], int numValues)
{
	for (int count = 0; count < numValues; count++)
		InsertItem(values, 0, count);
}
  • Python Implementation
    def insertion_sort(array):
    for i in range(1, len(array)):
        for j in range(i, 0, -1):
            if array[j] < array[j - 1]:
                array[j], array[j - 1] = array[j - 1], array[j]
            else:
                break
    return array

Quick Sort

  • pivot을 중심으로 pivot 앞에는 pivot보다 작은 item, pivot 뒤에는 pivot보다 큰 item으로 나누는 과정을 반복하는 정렬 방식
  • Devided Conquar: 핸들링할 수 있는 수준까지 잘라서 해결
  • Time Complexcity

    • 이상적으로 반씩 쪼갰을 때

      • pivot을 지정하고 split을 실행하는 것 logN 시행
        • split이 시행될 때마다 pivot 기준으로 자리를 재배열하는 과정에서 N 소요
        • 시간복잡도 O(N * logN)

    • 이미 정렬돼 있는 요소를 정렬했을 때
      - split 후 반환되는 splitPoint가 정렬 순서로 나오기 때문에 split N번 실행
      - split이 실행될 때마다 pivot과 값 N 번 비교
      - 계산복잡도 O(N^2)

      https://velog.velcdn.com/images/morion002/post/418c511b-c98d-4f59-b989-4e2b42d0b0de/quick.jpg

  • C++ Implementation
    int Split(int values[], int first, int last) {
	int pivot, temp;
	int low, high;

	low = first + 1;
	high = last;
	pivot = values[first];

	while (low < high) {
		while (low <= last && values[low] < pivot)
			low++;
		while (high >= first && values[high] > pivot)
			high--;
		if (low < high) {
			temp = values[low];
			values[low] = values[high];
			values[high] = temp;
		}
	}
	temp = values[first];
	values[first] = values[high];
	values[high] = temp;
	return high;
}

void QuickSort(int values[], int first, int last) {
	if (first < last) {
		int splitPoint = Split(values, first, last);
		QuickSort(values, first, splitPoint - 1);
		QuickSort(values, splitPoint + 1, last);
	}
}
  • Python Implementation
    def quick_sort(array, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        while left <= end and array[left] <= array[pivot]:
            left += 1
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right:
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]
        quick_sort(array, start, right -1)
        quick_sort(array, right + 1, end)
        return array

def quick_sort_two(array):
    if len(array) <= 1:
        return array
    pivot = array[0]
    tail = array[1:]

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

    return quick_sort_two(left_side) + [pivot] + quick_sort_two(right_side)

Count Sort

  • 특정한 조건이 부합할 때만 사용할 수 있는 매우 빠른 정렬 알고리즘
  • 요소 값들끼리 서로 비교하지 않고 정렬하는 알고리즘
  • 배열 내 최대값 +1 만큼의 길이 배열이 필요하기 때문에 메모리 낭비 가능성
  • 배열 내에 원소 값들의 개수를 저장하는 Counting Array 생성 필요
  • counting array의 각각의 요소들에 대해 직전 요소들의 값 더하기
  • 입력 배열과 동일한 크기의 출력 배열을 만들고 입력 배열의 역순으로 출력 배열에 요소들 채우기
  • O(N)의 시간 복잡도
  • C++ Implementation
    void counting_sort(int* arr, int size)
{
	int* counting, *sorted;
	int maxNum = 0;
	for (int i = 0; i < size; i++) if (arr[i] > maxNum) maxNum = arr[i];
	counting = new int[maxNum + 1]{0};
	sorted = new int[size] {0};

	for (int i = 0; i < size; i++) counting[arr[i]]++;
	for (int i = 1; i <= maxNum; i++) counting[i] += counting[i - 1];
	for (int i = 0; i < size; i++)
	{
		sorted[counting[arr[i]] - 1] = arr[i];
		counting[arr[i]]--;
	}
	for (int i = 0; i < size; i++) arr[i] = sorted[i];

	delete[] counting;
	delete[] sorted;
}
  • Python Implpementaion
    def counting_sort(array):
    result = []
    count = [0] * (max(array) + 1)
    for i in range(len(array)):
        count[array[i]] += 1
    for i in range(len(count)):
        for j in range(count[i]):
            result.append(i)
    return result

Python Sorting Library

  • 기본 정렬 알고리즘인 sorted()
  • Quick sort와 동작 방식이 비슷한 병합 정렬 기반
  • 최악의 경우 시간 복잡도 O(N*logN)

Practice

위에서 아래로

  • 문제
    • 하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관 없이 무작위로 주어짐
    • 이 수를 큰수 부터 작은 수까지 내림차순으로 정렬하면되는 문제
    • 즉 수열을 내림차순으로 정렬하는 프로그램을 생성
  • 입력 조건
    • 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. 이때 범위는 1 <= N <= 500
    • 둘째 줄부터 N + 1 번째 줄 까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하 자연수
  • 출력 조건
    • 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분해서 출력하면된다. 동일한 수는 순서상관없다.
n = int(input())

array = []
for i in range(n):
    array.append(input())

print(sorted(array))

성적이 낮은 순서로 학생 출력하기

  • 문제
    • N명의 학생 정보
    • 학생 정보는 학생의 이름과 학생의 성적으로 구분
    • 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성
  • 입력 조건
    • 첫 번째 줄: N, K 가 공백으로 구분되어 입력 (1 <= N <= 100,000, 0 <= K <= N)
    • 두 번째 줄: 배열 A의 원소들이 공백으로 구분되어 입력 (원소 a < 10,000,000인 자연수)
    • 세 번째 줄: 배열 B의 원소들이 공백으로 구분되어 입력 (원소 b < 10,000,000인 자연수)
  • 출력 조건
    • 최대 K번 바꿔치기 연산을 수행해서 가장 최대의 합을 갖는 A의 모든 원소 값의 합을 출력
n = int(input())

array = []
for i in range(n):
    array.append(list(input().split()))

array.sort(key = lambda student: student[1])

for i in range(n):
    print(array[0])

두 배열의 원소 교체

  • 문제
    • 동빈이는 두 개의 배열 A와 B를 가지고 있음
    • 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는모두 자연수
    • 동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것
    • 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것
    • N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성
  • 입력 조건
    • 첫째 줄에 N, M, K의 자연수가 주어지며, 각 자연수는 공백으로 구분
    • 둘째 줄에 N개의 자연수가 주어지며 각 자연수는 공백으로 구분
    • 입력으로 주어지는 K는 M보다 항상 작거나 같음
  • 출력 조건
    • 큰 수의 법칙에 따라 더해진 답

n, k = map(int, input().split())

array_one = list(map(int, input().split()))
array_two = list(map(int, input().split()))

array_one.sort()
array_two.sort(reverse=True)

for i in range(k):
    if array_one[i] < array_two[i]:
        array_one[i], array_two[i] = array_two[i], array_one[i]

print(sum(array_one))
profile
Huisu
이전 포스트

DFS/BFS

다음 포스트

Binary Search

0개의 댓글