[1. 개요]
각 언어 별 배열을 정렬하는 방법을 정리하도록 한다.
각 언어 별 표준 라이브러리에서 제공하는 정렬은 보통 O(nlogn) 으로 구현되어 있다.
기본적으로 오름차순으로 정렬하는 방법을 정리하고,
내림차순은 정렬 판단 시 사용 되는 함수를 반대로 구현하거나
배열을 역순으로 조회하면 된다.
[2. C언어]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> // qsort | |
// 오름차순 정렬을 위해서 | |
// L 에 저장 된 값이 R 에 저장된 값 보다 정렬 기준 상 | |
// 작을 경우=> 음수를 반환 | |
// 같을 경우=> 0을 반환 | |
// 클 경우=> 양수를 반환 | |
// | |
// 인접한 원소를 비교 할 때, | |
// _L 은 배열 순서 상 왼쪽에 | |
// _R 은 배열 순서 상 오른쪽에 옴 | |
// | |
// 정렬을 위한 swap 이 필요 할 때 => 음수를 반환한다. | |
int comp(const void *const _L, const void *const _R) | |
{ | |
const int *const p1 = (int*)_L; | |
const int *const p2 = (int*)_R; | |
// 배열의 첫번째 원소가 같을 경우 | |
// 두번째 원소를 기준으로 정렬 | |
if (p1[0] == p2[0]) { | |
return p1[1] - p2[1]; | |
} | |
return p1[0] - p2[0]; | |
} | |
// 길이가 2인 배열을 원소로 갖는 | |
// 배열을 정렬 | |
int main() | |
{ | |
int mylist[10][2] = { | |
{3, 5}, | |
{2, 7}, | |
{9, 6}, | |
{5, 4}, | |
{3, 5}, | |
{7, 7}, | |
{5, 3}, | |
{1, 8}, | |
{6, 3}, | |
{4, 11} | |
}; | |
// 정렬 할 배열의 길이 == 10 | |
// 배열의 한 원소의 크기 == 8 | |
// 대소비교 판단을 위한 함수 | |
qsort(mylist, 10, sizeof(int)*2, comp); | |
for (int i=0; i<10; i++) { | |
printf("(%d, %d)\n", mylist[i][0], mylist[i][1]); | |
} | |
return 0; | |
} |
[3. C++]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <algorithm> // std::sort() | |
struct data | |
{ | |
int a; | |
int b; | |
// operator< 을 오버로딩하여 | |
// 정렬 기준을 제시 할 수 있음. | |
// | |
// 단, 아래 방법이 여러 언어에서 정렬을 위해 | |
// 공통으로 작성하는 방식 (L, R) | |
}; | |
struct cmp | |
{ | |
// 구조체 연산자 오버로딩 | |
// 정렬에서 인접한 두 원소 중 | |
// L 은 순서 상 앞쪽에 | |
// R 은 순서 상 뒤쪽에 옴 | |
// | |
// 정렬을 위해 | |
// swap 이 필요할 경우 true 를 반환하도록 함 | |
// 필요하지 않는 경우 false 를 반환하도록 함. | |
// | |
bool operator()(const data &L, const data &R) const | |
{ | |
// 정렬 기준 상 | |
// 변수 a 가 같은 경우 | |
// b 를 기준으로 오름차순 정렬을 하도록 함 | |
if (L.a == R.a) { | |
return L.b < R.b; | |
} | |
return L.a < R.a; | |
} | |
}; | |
int main() | |
{ | |
std::vector<data> mylist; | |
mylist.reserve(10); | |
mylist.push_back({3, 5}); | |
mylist.push_back({2, 7}); | |
mylist.push_back({9, 6}); | |
mylist.push_back({5, 4}); | |
mylist.push_back({3, 5}); | |
mylist.push_back({7, 7}); | |
mylist.push_back({5, 3}); | |
mylist.push_back({1, 8}); | |
mylist.push_back({6, 3}); | |
mylist.push_back({4, 11}); | |
std::sort(mylist.begin(), mylist.end(), cmp{}); | |
for (const auto &data : mylist) { | |
std::cout << data.a << ", " << data.b << '\n'; | |
} | |
return 0; | |
} |
[4. go]
=> 기타 알고리즘 문제 풀이 참조
[5. python]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
mylist = [ | |
[3, 5], | |
[2, 7], | |
[9, 6], | |
[5, 4], | |
[3, 5], | |
[7, 7], | |
[5, 3], | |
[1, 8], | |
[6, 3], | |
[4, 11] | |
] | |
# 첫번째 데이터로만 기준 | |
newlist = sorted(mylist, key = lambda x: x[0]) | |
print(newlist) | |
# 첫번째 데이터가 같을 경우 | |
# 두번째 데이터를 기준으로 | |
mylist.sort(key = lambda x: (x[0], x[1])) | |
print(mylist) |
[6. rust]
=> 작성 필요