질문과 답변

간단한 정렬 질문 두변째 입니다 날짜:2020-3-5 11:36:32 조회수:136
작성자 : Program
포인트 : 55
가입일 : 2020-02-13 11:49:35
방문횟수 : 26
글 6개, 댓글 10개
소개 : 재미있는 프로그램
작성글 보기
쪽지 보내기

이 앞번 질문의 코드가 아래와 같은데
여기는 순환변수 i,k, 둘다 변위0 즉 처음부터 순회하는데
for(i=0;i<num;i++)//0부터 끝 num까지 순회하면서
{
   // for(k=0;k<num;k++)//마찬가지 0부터 <====여기를 주석처리하고 아래 라인 처럼 

     for(k=i+1;k<num;k++) //<=== 이렇게 바꾸면 어떻게 되는가?

    {
        if(ar[i] < ar[k]) // ar[i] 와 ar[k] 크기를 비교하여 
        {
             imsi=ar[i]; //임시변수에 ar[i]를 잠시 넣어두고
             ar[i]=ar[k]; //i 변위와 k 변위의 값을 교환한다
             ar[k]=imsi; //마지막 임시저장값을 교환해 준다
        }
    }
}

이렇게 두번째 변수 k를 0부터 비교하지 않고 앞변수 다음부터 즉 i+1부터 비교하면

비교횟수는 많이 줄어드는데 과연 이 코드가  정렬을 잘 해 내는지 궁금합니다.

머리로 생각만 해보니 답이 잘 안나와서 질문합니다 감사합니다


목록보기 삭제 수정 신고 스크랩

코딩페인트 3월5일 1:03:29  

결국은 똑같은 순차정렬 입니다.
정렬은 잘되겠지만 시간복잡도는 n^2 입니다.
적은수의 데이터는 하드웨어 성능이 좋아서 문제는없지만
데이터량이 많아지면 정렬할때에는 오래걸릴꺼에요

코딩페인트 3월5일 1:04:40  

제가 옛날에 빅데이터쪽에서 일한적이 있는데 기본적으로 데이터량이 페타바이트단위로 들어왔습니다.

그정도 양일때 저런식으로 정렬을 하게되면 하루종일 돌아도 데이터 정렬이 안되겠죠...

Program 3월17일 1:17:11  

그러면 이부분을 정렬코딩을 예시로 한번 보여주시면 어떨까요?
나는 지금까지 어떻게 코딩을 해야 할지 알맞은 답을 찾지 못앴거던요
for(i=0;i<num;i++)
{
    // for(k=0;k<num;k++)
    for(k=i+1;k < num; k++)
    {
        if(ar[i] < ar[k]) // ar[i] 와 ar[k] 크기를 비교하여
        {
            imsi=ar[i]; //임시변수에 ar[i]를 잠시 넣어두고
            ar[i]=ar[k]; //i 변위와 k 변위의 값을 교환한다
            ar[k]=imsi; //마지막 임시저장값을 교환해 준다
       }
    }
}

즉 자료(구조체) num개를 저정한 배열 ar[num-1] 개 있을때
ar[n].bunho > ar[n+1].bunho; 대략 이렇게 된다고 하면
또는 그냥 ar[n] > ar[n+1] ; 즉 ar배열 자체가 int 배열이라고 봐도 됩니다.

답변 코드를 기대해 봅니다
 


로그인하셔야 댓글을 달 수 있습니다.