알고리즘_7_기초 정렬 알고리즘 문제 풀이

Aug 8, 2021 » writing

K 실전 알고리즘 강좌(Algorithm Programming Tutorial) 동빈나 님 수업을 참고하여 작성하였습니다

7_기초 정렬 알고리즘 문제 풀이

정의

기초 정렬 알고리즘 문제 풀이

1. 기초 정렬 문제 풀어보기

1) 숫자 세 개가 주어졌을 때, 가장 작은 수, 그 다음 수, 가장 큰 수를 출력하는 프로그램을 작성하시오.

#include <stdio.h>

int array[3];

int main(void) {
	int number, i, j, min, index, temp;
	for (i = 0; i< 3; i++) {
		scanf("%d", &array[i]);
	}
	for (i = 0; i< 3; i++) {
		min = 10000001;
		for (j = i; j< 3; j++) {
			if (min > array[j]) {
				min = array[j];
				index= j;
			}
		}
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}
	for (i = 0; i< 3; i++) {
		printf("%d " , array[i]);
	}
	return 0;
}
// 3 1 2
// 1 2 3

2) N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다

#include <stdio.h>

int array[1001];

int main(void) {
	int number, i, j, min, index, temp;
	scanf("%d", &number);
	for (i = 0; i< number; i++) {
		scanf("%d", &array[i]);
	}
	for (i = 0; i< number; i++) {
		min = 1001;
		for (j = i; j< number; j++) {
			if (min > array[j]) {
				min = array[j];
				index= j;
			}
		}
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}
	for (i = 0; i< number; i++) {
		printf("%d \n" , array[i]);
	}
	return 0;
}

// 5
// 5
// 2
// 3
// 4
// 1
// 1
// 2
// 3
// 4
// 5

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다

#include <stdio.h>

int number;
int data[1000000];
	
void quickSort(int* data, int start, int end) {
	if (start >= end) {		// 원소가 1개인 경우 그대로 두기 
		return;
	}
	
	int key = start; // 키는 첫번째 원소 (pivot)
	int i = start + 1;
	int j = end;
	int temp;
	
	while (i <= j)  {	// 엇갈릴 때까지 반복 
		while (data[i] <= data[key]) {	// 키 값보다 큰 값을 만날 때까지 
			i++;
		}
		while ( j > start && data[j] >= data[key]) {		// 키 값보다 작은 값을 만날 떄까지 
			j--;
		}
		if (i > j) {	// 현재 엇갈린 상태면 키 값과 교체
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		} 
		else {	// 엇갈리지 않았다면 i와 j 교체
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;		
		}
	} 
	quickSort(data, start, j -1);
	quickSort(data, j+1, end);
}

int main(void) {
	scanf("%d", &number);
	for (int i =0; i< number; i++) {
		scanf("%d", &data[i]);
	}
	quickSort(data, 0, number - 1);
	for (int i = 0; i< number; i++) {
		printf("%d \n", data[i]);
	}
	return 0;
}
// 5
// 5
// 4
// 3
// 2
// 1
// 1
// 2
// 3
// 4
// 5