[객체지향프로그래밍] 8. 연속 데이터 2

안녕하세요!! 코딩하는 경제학도 쏘코입니다.

오늘은 연속적인 데이터를 정렬하고, 검색하고, 나열하는 방법에 대해서 알아보도록 하겠습니다!

0. 정렬

정렬에는 다양한 방법이 있습니다.

버블정렬, 선택정렬, 삽입정렬부터 시작해서 조금 더 빠른 퀵정렬, 합병정렬, 힙정렬 등등이 있는데,

이것들은 자료구조나 알고리즘 시간에 배울 것들이지 C++를 배우는 입장에서 이런 것들까지 굳이 배울 필요는 없기 때문에 이번 예시에서는 선택정렬을 통해 정렬함수를 만드는 방법을 알아보겠습니다.

값을 바꾸는 swap함수, 출력하는 print함수를 기본으로 만들어주고, 정렬을 위한 selection_sort 함수를 만들었습니다.

앞에서부터 쭉 찾으면서 가장 작은 요소를 맨 앞 요소랑 바꿔주고,

그 다음에 작은 요소를 찾아서 두 번째 요소와 바꿔주고..를 마지막까지 반복한 것이 선택정렬입니다.

코드가 길기 때문에 잘 안보이시거나, 복사가 필요하신 분이 있을까 싶어 코드부분만 따로 올립니다.

#include <iostream>
#include <vector>
void swap(int& a, int& b) { // std::swap, <algorithm>
	int temp = a;
	a = b;
	b = temp;
}
void selection_sort(std::vector<int>& a) {
	int n = a.size();
	for (int i = 0; i < n - 1; i++) {
		int small = i;
		for (int j = i + 1; j < n; j++)
			if (a[j] < a[small])
				small = j; // Found a smaller value
		if (i != small)
			swap(a[i], a[small]);
	}
}
void print(const std::vector<int>& a) {
	int n = a.size();
	if (n > 0) {
		for (int i = 0; i < n; i++)
			std::cout << a[i] << ' ';
	}
	std::cout << '\n';
}
int main() {
	std::vector<int> list{ 23, -3, 4, 215, 0, -3, 2, 23, 100, 88, -10 };
	std::cout << "Before: ";
	print(list);
	selection_sort(list);
	std::cout << "After: ";
	print(list);
}

정렬이 더 알고 싶으신 분은 알고리즘 파트에서 기본적인 정렬 방법에 대해 작성한 게시물이 있으니 참고하시면 좋을 것 같습니다 :)

[알고리즘분석] 6. 계산복잡도 : 정렬

이번 포스팅의 주제는 계산복잡도, 그 중에서도 정렬의 계산복잡도입니다. 어떤 알고리즘의 효율을 측정할 때는 시간복잡도와 공간복잡도를 생각합니다. 그리고 문제를 풀 때는 두 가지 케이스

ssocoit.tistory.com