현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

삽입정렬과 버블정렬 구분하기. 어렵습니다.

lokee의 이미지
글쓴이: lokee / 작성시간: 금, 2006/08/25 - 3:28오후

저희대학 컴공과 교수님이 C문제를 내주셨습니다.

실행파일만 주셧습니다. C코드는안보이구요.

C프로그램을 시키고나서 알파벳 input 을 넣는대요,

무작위input

정렬된input

역정렬된 input 을 넣었는데

이게 도무지 버블정렬인지 삽입정렬인지 알수가업네요.

참고로 time 명령을 실행해본결과는 두정렬모두 걸리는시간이 너무비슷하다는겁니다.

100,000 input 을 입력하면

랜덤 / 오름차순정렬 / 내림차순정렬

삽입정렬 250 / 140 / 360
버블정렬 270 / 150 / 370

이렇게 나오는데 어떤 input 을 넣어봐야 주어진프로그램이 버블정렬인지 삽입정렬인지 알수가있을까요?

(제가넣어본건 이 세가지 종류의 input 뿐입니다.)


이문제 정말어렵다고 소문난문제입니다.

움...누구 아이디어 없으세요? 좀 도와주시죠.

Forums: 
프로그래밍 QnA
익명사용자의 이미지

글쓴이: 익명사용자 / 작성시간: 금, 2006/08/25 - 3:39오후

프로그램 동작을 보고 프로그램이 어떤 정렬알고리즘을 쓰는지 맞추는 것인가요 ???
재미있는 문제로군요.(푸는 입장에서는 괴롭겠습니다만...)

한번 같은 입력을 넣어보는 건 어떨까요 ??? (1 을 100,000 개 넣는다던가...)
해결책이 될것 같지는 않습니다만...

정 방법이 없으면 디컴파일을 해보심이...

ironiris의 이미지

글쓴이: ironiris / 작성시간: 금, 2006/08/25 - 5:37오후

값들이 옆에 있는 것들끼리 교체가 일어나면 버블소트
그게 아니면 삽입소트

grassman의 이미지

글쓴이: grassman / 작성시간: 금, 2006/08/25 - 6:42오후

삽입 정렬은 정렬된 데이터에 작은 값이 들어가면 느려진다는 점을 이용해보면 어떨까 합니다.

예를들어

n개의 데이터가 있다면

2, 3, 4, ... n, 1

이런식으로 입력하는거죠.

이렇게 하면 삽입정렬의 비교 횟수는 2*n회 정도 될 겁니다. 데이터 교환 횟수는 2*n회 정도가 될거고요.
(자기 자리에 다시 집어넣는 경우 포함)
반면 버블 소트라면 비교 횟수는 n^2회에 데이터 교환 횟수는 n회 정도 되겠죠.

n이 아주 큰 수면 두 알고리즘간에 시간 차이가 나타나지 않을까 합니다.

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.