Algorithm 공부 #06 - 정렬(삽입 정렬과 퀵 정렬)

 

Algorithm 공부 #06 - 정렬(삽입 정렬과 퀵 정렬)

 

삽입 정렬(Insertion Sort)

    ● 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입하며 정렬하는 방식

    ● 시간 복잡도는 O(n^2)으로 느린 편이지만 구현 난이도는 쉬움

    ● 적절한 삽입 위치를 탐색하는 부분에서 이진 탐색 등과 같은 탐색 알고리즘을 사용하여 시간 복잡도 줄일 수 있음     

    ● 삽입 정렬 과정       

         1. 현재 index에 있는 데이터 값을 선택

         2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색

         3. 삽입 위치부터 index가 있는 위치까지 shift 연산을 수행

         4. 삽입 위치에 현재 선택한 데이터를 삽입하고 indexx++ 연산을 수행

         5. 현재 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복

         

 

백준 11399번 ATM

https://www.acmicpc.net/problem/11399

11399번: ATM

 

※ N이 1000이하이므로 O(n^2)의 삽입 정렬을 이용해도 무방 ※

● 인출 시간이 가장 적게 걸리는 사람이 가장 먼저 인출할 수 있도록 순서를 정하기(그리디 방식)

 

#include<iostream>
#include<vector>
using namespace std;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	
	vector<int>A(N, 0); // 입력받을 배열
	vector<int>S(N, 0); // 합 배열

	for (int i = 0; i < N; i++)
		cin >> A[i]; // 배열 입력받기

	for (int i = 1; i < N; i++) {
		int insert_point = i; // 삽입할 포인트
		int insert_value = A[i]; // 그 값

		for (int j = i - 1; j >= 0; j--) { // 뒤에서부터 비교하며 
			if (A[i] > A[j]) {			   // value를 삽입할 곳 탐색
				insert_point = j + 1; // A[i]가 A[j]보다 크면 A[j]옆에 바로 A[i]를 놓으면 됨
				break;
			}					 
			if (j == 0)
				insert_point = 0;
		}
		for (int j = i; j > insert_point; j--)
			A[j] = A[j - 1]; // 최초의 데이터를 선택했던 지점부터 삽입할 지점까지 배열을 한 칸씩 뒤로 밀어줌
		
		A[insert_point] = insert_value; // 정렬된 범위에 데이터 삽입
	}
	
	S[0] = A[0];
	int sum = 0;

	for (int i = 1; i < N; i++)
		S[i] = S[i - 1] + A[i]; // 누적 합 만들기

	for (int i = 0; i < N; i++)
		sum += S[i];

	cout << sum;
}

 

 

 

퀵 정렬(Quick Sort)

    ● pivot값을 기준으로 해당 값보다 작은 테이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘

    ● 기준값 선정에 따라서 시간 복잡도에 많은 영향을 줌

    ● 평균 시간 복잡도는 O(nlogn)이며 최악의 시간 복잡도는 O(n^2)     

 

 

백준 11004번 k번째 수

https://www.acmicpc.net/problem/11004

 

※ pivot을 정하는 방법 ※

● pivot == k : K번쨰 수를 찾은 것으므로 알고리즘을 종료

● pivot > k : pivot의 왼쪽 부분에 k가 있으므로 왼쪽(S~pivot-1)을 정렬을 수행

● pivot < k : pivot의 오른쪽 부분에 k가 있으므로 오른쪽(pivot+1~E)만 정렬을 수행

 

#include<iostream>
#include<vector>
using namespace std;

void quickSort(vector<int>& A, int start, int end, int k);
int partition(vector<int>& A, int start, int end);
void swap(vector<int>&A, int i, int j);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, K;
	cin >> N >> K;

	vector<int>A(N, 0);
	for (int i = 0; i < N; i++)
		cin >> A[i];

	quickSort(A, 0, N - 1, K - 1);
	cout << A[K - 1];
}

void quickSort(vector<int>& A, int start, int end, int K) {
	int pivot = partition(A, start, end);
	if (pivot == K)
		return;
	else if (pivot > K)
		quickSort(A, start, pivot - 1, K);
	else
		quickSort(A, pivot + 1, end, K);
}

int partition(vector<int>& A, int start, int end) {
	if (start + 1 == end) {
		if (A[start] > A[end])
			swap(A, start, end);
		return end;
	}

	int middle = (start + end) / 2;
	swap(A, start, middle);
	int pivot = A[middle];
	int i = start + 1;
	int j = end;

	while (i <= j) {
		while (j >= start + 1 && pivot < A[j])
			j--;
		while (i <= end && pivot > A[i])
			i++;
		if (i > j)
			swap(A, i++, j--);
		else
			break;
	}

	A[start] = A[j];
	A[j] = pivot;
	return j;
}
void swap(vector<int>& A, int i, int j) {
	int temp = A[i];
	A[i] = A[j];
	A[j] = temp;
}