[C++] 정렬 알고리즘 - 선택 정렬/삽입 정렬/버블정렬

2022. 10. 11. 19:51·Programming Languages/C와 C++
728x90

1.선택 정렬

int a[10] = {7, 5, 2, 10, 8, 4, 3, 1, 6, 9};

선택 정렬은 이 중에서 가장 작은 데이터를 선택해서 맨 앞의 데이터와 바꾸고 그 다음으로 작은 데이터를 선택해서 앞에서 두번째인 데이터와 바꾸는 작업을 반복해서 수행한다. 
항상 가장 작은 데이터를 선택해서 정렬하는 방법이다.  

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


int a[10] = {7, 5, 2, 10, 8, 4, 3, 1, 6, 9};
int main(void) {
    for (int i = 0; i < 10; i++) {
        int min_value = a[i]; // 우선 i번쨰 값을 mininum으로 설정
        int min_idx = i;
        for (int j = i+1; j < 10; j++) {
            if (min_value > a[j]) {
                min_value = a[j];
                min_idx = j; // min 값 갱신하기
            }
        }
        // 최소값과 배열의 i번째 값과 자리 바꾸기
        swap(a[i], a[min_idx]);
    }
    
    // 출력하기
    for (int i = 0; i < 10; i++) {
        cout << a[i] << " ";
    }
    return 0;
}



2. 삽입 정렬 

첫번쨰 원소는 우선 정렬되었다고 가정한다. 그리고 두번쨰 원소부터 비교를 시작한다. 

7, 5, 2, 10, 8, 4, 3, 1, 6, 9

5, 7, 2, 10, 8, 4, 3, 1, 6, 9 -> 5는 7보다 작으므로 7 과 자리를 바꾼다 

3, 5, 7, 10, 8, 4, 2, 1, 6, 9 -> 3은 5보다 작으므로 5의 앞에 삽입한다 

3, 5, 7, 10, 8, 4, 2, 1, 6, 9 -> 10은 3, 5, 7 보다 크므로 자리 이동을 하지 않는다. 

... 위의 과정을 반복한다. 


즉, 현재 확인 중인 원소가 더 이상 앞으로 갈 수 없으면, 그 곳이 삽입할 위치이다. 즉 자기 자신보다 작은 수를 만나면 삽입할 위치에 대한 탐색을 종료한다. 

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


int a[10] = {7, 5, 2, 10, 8, 4, 3, 1, 6, 9};
int main(void) {
    
    for (int i = 1; i < 10; i++) {
        for (int j = i; j >= 0; j--) {
            if (a[j] < a[j-1]) { // 자기 자신보다 크면 swap
                swap(a[j], a[j-1]);
            } else { // 더이상 앞으로 갈 수 없으면 그 곳에서 삽입하기 -> 자기 자신보다 작은 수를 만나면 break
                break;
            }
        }
    }
    
    // 출력하기
    for (int i = 0; i < 10; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

 

3. 버블 정렬 


버블 정렬은 매번 배열의 다음 인덱스 값과 자신의 값을 비교하여 자리를 이동시킨다. 

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


int a[10] = {7, 5, 2, 10, 8, 4, 3, 1, 6, 9};
int main(void) {
    int temp;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10 - i -1; j++) {
            if (a[j] > a[j+1]) { // 현재 위치 값보다 다음 위치의 값이 더 작을 경우 값을 바꾼다
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
    
    // 출력하기
    for (int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}
728x90

'Programming Languages > C와 C++' 카테고리의 다른 글

Compiled Languages vs Interpreter Languages  (0) 2022.02.04
[C언어] 값에 의한 호출 vs 참조에 의한 호출  (0) 2021.12.17
C언어 문자열 처리를 위한 포인터 char* 과 배열 char[] 비교  (0) 2021.12.14
C언어 enum (열거형)  (0) 2021.12.14
C언어 공용체  (0) 2021.12.14
'Programming Languages/C와 C++' 카테고리의 다른 글
  • Compiled Languages vs Interpreter Languages
  • [C언어] 값에 의한 호출 vs 참조에 의한 호출
  • C언어 문자열 처리를 위한 포인터 char* 과 배열 char[] 비교
  • C언어 enum (열거형)
minjiwoo
minjiwoo
Data Engineering과 Cloud Native 기술에 대해 Dive Deep 하는 플랫폼 엔지니어가 되는 것을 목표로 하고 있습니다. 경험과 공부한 내용을 기록하며 지속가능한 엔지니어가 되는 것이 꿈입니다.
minjiwoo
minji's engineering note
minjiwoo
전체
오늘
어제
  • 분류 전체보기 (613)
    • Data Engineering (42)
      • Apache Spark (11)
      • Databricks & Delta Lake (9)
      • Airflow (3)
      • SQL (6)
      • Trouble Shooting (2)
      • Hadoop (2)
      • MLOps (1)
    • Cloud Engineering (104)
      • AWS (23)
      • Linux 🐧 (29)
      • Docker 🐳 (21)
      • Kubernetes ⚙️ (20)
      • Ansible (10)
    • Computer Science (87)
      • 네트워크 (9)
      • 운영체제 (25)
      • 정보처리기사 (48)
      • CS 기술 면접 스터디 (3)
    • Programming Languages (27)
      • Python (17)
      • C와 C++ (10)
    • Backend (5)
      • Django (2)
    • 프로젝트 (2)
      • 테크포임팩트 (2)
    • iOS (11)
      • 레이블러리 (2)
    • Algorithm (PS) (275)
      • LeetCode (6)
    • 개발일기 (30)
      • 내돈내산 후기🎮 (3)
      • 개발자 취준생 (5)
      • Today I Learned (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • Hi there

인기 글

태그

  • 스파크
  • SPARK
  • 백준
  • dp
  • 데이터브릭스
  • ansible
  • 클라우드
  • 데이터엔지니어
  • 쿠버네티스
  • 파이썬
  • 백트래킹
  • 데이터엔지니어링
  • Leetcode
  • Databricks
  • python
  • EC2
  • docker
  • AWS
  • 리눅스
  • 빅데이터
  • 코딩테스트
  • linux
  • Swift
  • Kubernetes
  • 프로그래머스
  • 알고리즘
  • 카카오코딩테스트
  • 운영체제
  • dfs
  • BFS

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
minjiwoo
[C++] 정렬 알고리즘 - 선택 정렬/삽입 정렬/버블정렬
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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