HotFoxy
불여우의 전직 이야기
게임 서버 개발자가 되어 보죠!
전체 방문자
오늘
어제
  • 분류 전체보기 (135)
    • 연구한 이야기 (26)
      • 깊게 공부해보기 (7)
      • 문제 해결 이야기 (12)
      • 맡은 업무 이야기 (6)
    • 전직 이야기 (0)
      • 1년이라는 시간 (5)
      • 프로카데미 이야기 (5)
    • 공부한 이야기 (87)
      • 알고리즘 (7)
      • 리눅스 (11)
      • 클라우드 (24)
      • 윈도우 OS (17)
      • 윈도우 소켓 프로그래밍 (11)
      • 네트워크 (16)
      • Docker & K8S (0)
      • 기타 (1)
    • 자격증 이야기 (12)
  • MSB : Mad Square's Brawl
  • GITHUB

인기 글

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
HotFoxy
공부한 이야기/알고리즘

정렬 - 기본기

공부한 이야기/알고리즘

정렬 - 기본기

2022. 8. 7. 15:54

기본 다지기 - 정렬

정렬이야말로 기본기 중 가장 밑단이면서도, 모든 알고리즘의 대표격이라고 생각한다.

여러 정렬의 종류를 알아보고, 새로운 정렬 방식이 있는지, 그것의 복잡도는 어떻게 계산되는지 생각해 보자.

 

정렬이란

비교 가능한 요소를 가지고 있는 데이터셋의 연속 (배열이나 리스트 등) 에서, 특정한 조건을 기준으로 요소들의 순서를 재배치 하는 방법론이다.

일반적으로 특정 값을 오름차순, 내림차순으로 순서를 매기는 것이 대표적이다.

하지만 특정 값에 가장 가까운 순서라던지, 특정 계산식을 거쳤을 때 원하는 값에 가깝게 나오는 순서라던지 등등 확장은 마음껏 가능할것 같다.

물론 이들도 결국 계산식을 거친 후 그 값에 의한 오름 내림차순이기는 하겠지만.

 

들어가기 앞서

swap

두 요소 간 배열 등 연속된 자료형에서의 순서를 바꿔주는, 즉 둘의 메모리에서의 위치를 변경해주는 swap 함수이다.

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
    return;
}

이를 라이브러리나 내장함수를 통해 쉽게 처리할 수 있는 방법이 있을까?

C에서는 템플릿이 존재하지 않기 때문에, 구현한다면 인자 형식이 void* 이 될 텐데, 이는 type-safe 하지 않다.
출처

그렇다면 C++ 템플릿을 적용해 이쁘게 짜보자.

template <typename T> 
void swap(T *a, T *b) {
    T temp = *a;
    *a = *b;
    *b = temp;
    return;
}

이제 이걸 C++ swap 함수와 비교해 보자.

template <class T>
void swap ( T& a, T& b )
{
  T c(a); a=b; b=c;
}

확실히, C++만의 특징이 몇 개 보인다.

첫째로, 참조자를 통해서 전달받게 바뀌었다. 물론 포인터를 사용한 것과 참조자를 사용한 것 모두 결과는 같고, 구문 형태상의 차이만 있지만, 훨씬 이쁘긴 하다.

둘째로, temp 역할을 하는 변수 선언 시 초기화를 곧바로 T c(a) 를 통해서 했다. 이는 T가 기본 자료형이 아니라, 커스텀 자료형이나, 생성자를 통해 특정 작업이 이루어지는 자료형에 대응하기 위함으로 보이며, 그렇게 생각하니 T temp = *a; 와 동일한 결과일 수 있겠지만, 더욱 안전하고 발전된 형태인 것 같다.

 

printArray

배열을 순서에 맞추어 출력해주는 printArray 함수이다.

void printArray(int *array, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return;
}

이 친구도 C++ template, 참조자를 통해서 더욱 이쁘게 바꿔줄 수 있을 것이다.

template <typename T>
void printArray(T &array, int size) {
    for (int i = 0; i < size; i++) {
        cout << array[i];
    }
    cout << endl;
    return;
}

C++ 에서는 iterator라던지 STL을 이용해서 배열이나 리스트를 다루는 함수가 수도 없이 많다.

 

generateRandomArray

이제 정렬 프로그램을 짜는 걸 도와줄, 랜덤으로 size 개의 int 배열을 만들어주는 generateRandomArray 메서드만 정의하고 넘어가자.

int* generateRandomArray(int size) {
    int *myArray = (int*) calloc(size, sizeof(int));
    srand((unsigned)time(NULL));
    for (int i = 0; i < size; i ++) {
        myArray[i] = rand() % 100;
    }
    return myArray;
}
저작자표시 (새창열림)

'공부한 이야기 > 알고리즘' 카테고리의 다른 글

정렬 - 힙정렬  (0) 2022.08.07
정렬 - 기수정렬  (0) 2022.08.07
정렬 - 삽입정렬  (0) 2022.08.07
정렬 - 선택정렬  (0) 2022.08.07
정렬 - 버블정렬  (0) 2022.08.07
  • 정렬이란
  • 들어가기 앞서
  • swap
  • printArray
  • generateRandomArray
'공부한 이야기/알고리즘' 카테고리의 다른 글
  • 정렬 - 기수정렬
  • 정렬 - 삽입정렬
  • 정렬 - 선택정렬
  • 정렬 - 버블정렬
HotFoxy
HotFoxy
1년 동안의 고군분투 전직 이야기! ..가 완료되어, 게임개발자로 살아남는 이야기!

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.