[C++ 때려잡기] C++ 기초강의 4-advenced 정렬과 탐색

2018/08/26 - [교육 노트/C++ 기초강의] - [C++ 때려잡기] C++ 기초강의 4-1 간단한 구조체

2018/08/26 - [교육 노트/C++ 기초강의] - [C++ 때려잡기] C++ 기초강의 4-2 배열과 다중배열

2018/08/26 - [교육 노트/C++ 기초강의] - [C++ 때려잡기] C++ 기초강의 4-3 마침내 포인터, 포인터 기초

2018/08/26 - [교육 노트/C++ 기초강의] - [C++ 때려잡기] C++ 기초강의 4-4 포인터와 배열의 상관관계, call by pointer

2018/08/26 - [교육 노트/C++ 기초강의] - [C++ 때려잡기] C++ 기초강의 4-5 동적할당

정렬 (소팅) 이란

Sorting (정렬)
데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일

이다

게임 랭킹, 성적순 정렬처럼 특정한 조건에 따라 순서를 재배열 하는것이다.

위의 그림은 작은 순서대로 정렬했다고 할 수 있다.

정렬방법에는 다양한 방법이 존재한다.

1. 삽입 정렬 (insertion sorting)

2. 선택 정렬 (selection sorting)

3. 거품 정렬 (bubble sorting)

인접한 두 원소를 비교 해나가는 방식

거품처럼 올라온다고 해서 버블 정렬이다

(짜기 쉬워서 쓴다)

위 3개가 상대적으로 쉬운 정렬 법에 속한다.

상대적으로 쉬워서 정렬하는데 걸리는 시간은 오래걸리는 편이다.

소팅이 말로 만들으면 이해가 되지않는다

그래서 시각화 사이트인

https://visualgo.net/en

를 참고해보면 된다.

sort탭에들어가서 다양한 정렬방법을 선택하여 눈으로 볼수있다.

실습으로 이제 위 3개의 정렬법을 직접짜보자, 너무 쉬우면 머지 소트까지 짜보자

탐색 (search)

탐색은 데이터가 어디에 위치하는지 찾는것이다.

예를들어 배열내에서 특정 숫자가 어디에 위치하는지 알고싶은경우 사용한다.

탐색방법은 크게 2가지 인데

1 순차 탐색

처음부터 원하는 데이터가 나올 때까지
순서대로 찾는 방식

설명이 필요없다. 걍 for문 다 돌려서 찾는거다

2. 이진탐색

업앤다운 게임처럼
중간에 위치한 값으로 비교해나가는 방식

이제 실습으로 이진 탐색을 구현해보자

시간복잡도

위와같은 알고리즘들이 얼마나 오래 걸리는지, 뭐가 더 좋은 속도를 내는지 등을 비교하기위해

시간 복잡도라는 개녕이 존재한다.

자세한 설명은 생략하겠지만

간단히 설명하면  어떤 알고리즘이 걸리는 시간을 의미하며
알고리즘을 구성한 명령어의 호출 빈도로 계산한다.

이제 이번시간에 배운 내용을 통하여 기존 가위바위보 게임에서 게임 순위를 구현한다.