글 읽기 - 이 문제는 버블정렬과 삽입정렬은 사용하지 말라는 문제죠??

injoon2018 5년 전 0

질문 게시판 보니 merge sort?를 사용하라고 하네요 nlogn 정렬을 사용해야하는데..

그렇다면 버블정렬, 삽입정렬 이런 것들은 그냥 학습용 정렬인가요??

#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;

int main(void)
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int number;
	
	cin >> number;
	string* arr;
	string temp;
	arr = new string[number];
	for (int i = 0; i < number; i++)
	{
		cin >> arr[i];
	}
	for (int i = 0; i < number; i++)
	{
		for (int k = 0; k < number-i; k++)
		{
			if ( (arr[k].length() > arr[k + 1].length()) || (arr[k].length()== arr[k + 1].length()) && arr[k] > arr[k+1])
			{
				temp = arr[k + 1];
				arr[k + 1] = arr[k];
				arr[k] = temp;
			}
		}
	}
	
	for (int i = 0; i < number; i++)
	{
		if (arr[i] == arr[i + 1])
			continue;
		cout << arr[i] << "\n";
	}
	system("pause");
	return 0;
}

djm03178 5년 전 1

버블 정렬은 실제로는 거의 쓸 일이 없습니다. 다만 코드가 간단하기 때문에 정렬 연습에 좋기도 하고, 시간복잡도를 배우는 데에도 기초 알고리즘으로 좋습니다.

삽입 정렬도 그 자체로는 그다지 쓰일 일이 없지만, 원소의 수가 매우 적은 경우에는 웬만한 "시간복잡도상 효율적인" 알고리즘들보다 빠르기 때문에 작은 범위에 대해서만 삽입 정렬을 수행하는 방식으로 효율적인 알고리즘을 변형해서 쓰이는 일이 많습니다. (하지만 이런 건 진.짜.겁.나.어.렵.습.니.다)

문제를 풀 때는 그냥 merge sort, heap sort 또는 피벗 선택을 매우 매우 잘 하는 quick sort 등을 사용하거나, 그냥 내장 라이브러리에 있는 정렬 함수를 쓰면 됩니다.

injoon2018 5년 전 0

감사합니다. 피벗 선택을 잘한다는 것은 무슨 말인가요??

djm03178 5년 전 1

보통 퀵 소트를 배울 때 오른쪽 끝, 왼쪽 끝의 원소를 피벗으로 잡고 구현하게 하는데 이렇게 하면 정렬된 상태, 모든 원소가 같은 상태를 효율적으로 처리하지 못한다는 뜻입니다.

injoon2018 5년 전 0

아하 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 문제는 버블정렬과 삽입정렬은 사용하지 말라는 문제죠??

injoon2018 5년 전 0

djm03178 5년 전 1

injoon2018 5년 전 0

djm03178 5년 전 1

injoon2018 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말