교환 정렬과 거품 정렬

오늘 회사의 플랫폼 코드를 읽을 때 정렬된 곳을 발견했는데 의외로 가장 원시적인 시간 복잡도 O(n의 제곱) 정렬 방식을 사용하고 있었다.
방금 그 코드들이 교환 정렬인지 거품 정렬인지 분간할 수 없는 걸 봤어요. 한 번은 면접에서 거품 정렬을 쓰라고 했는데 교환 정렬이라고 썼어요. 아무리 생각해도 부끄럽지 않았어요.
돌아와서 한 번 보고 나서야 문득 크게 깨달았다.사실 이 두 개는 모두 교실에서 배운 적이 있다.이러한 차이점은 다음과 같습니다.
먼저 거품 정렬:
정렬된 레코드 배열 R[1..n]을 수직으로 배열하고 각 레코드 R[i]는 무게를 R[i]로 간주합니다.키의 기포.가벼운 거품은 무거운 거품 아래에 있을 수 없다는 원칙에 따라 아래에서 위로 여러 그룹 R:
무릇 본 원칙에 어긋나는 가벼운 기포를 스캔하면 그것을 위로 띄운다.이렇게 반복해서 진행하면 마지막 두 개의 기포가 모두 가벼운 자는 위에 있고 무거운 자는 아래에 있다(이른바 청자는 천탁한 자는 땅이다)
code 예는 다음과 같습니다. (작은 것부터 큰 것까지)

void BubbleSort(int *vInt, size_t size )
{
        int temp;
        size_t i,j;
        for (i = 0; i < size; i++)
        {
                for (j = size - 1; j > i; j--)
                {
                        if (vInt[j] < vInt[j-1])
                        {
                                temp = vInt[j-1];
                                vInt[j-1] = vInt[j];
                                vInt[j] = temp;
                        }
                }
        }
}

그런 다음 정렬 스왑:
교환법의 절차는 가장 명확하고 간단하며 매번 현재의 원소를 하나하나 그 후의 원소와 비교하고 교환한다.(어릴 때부터 어른까지)

void ExchangeSort(int* pData,size_t Count)
{
        int iTemp;
        size_t i,j;

        for(i=0;i<Count-1;i++)
        {
                for(j=i+1;j<Count;j++)
                {
                        if(pData[j]<pData[i])
                        {
                                iTemp = pData[i];
                                pData[i] = pData[j];
                                pData[j] = iTemp;
                        }
                }
        }
}

위의 두 가지 정렬은 다음과 같이 확인할 수 있습니다.

int main(void)
{
        int i;
        int array[] = {12,18,81,-14,-1,0,33,38,46};
        int len = sizeof(array)/sizeof(int);

        printf("len is %d
",len);

        for(i = 0;i< len;i ++)
                printf("%d ",array[i]);
        printf("
");

        BubbleSort(array,len);

        for(i = 0;i < len; i ++)
                printf("%d ",array[i]);
        printf("

");

        return 0;
}

사실 엄밀히 말하면 거품 정렬도 교환 정렬의 일종에 속하는데 그들의 시간 복잡도는 모두 O(n의 제곱)이다.차이점:
거품이 생기면 내부의 순환이 비교적 연속되는 두 원소를 정렬하고, 그렇지 않으면 교환한다.
교환 정렬은 내부의 한 순환에서 모든 원소를 외부 순환의 원소와 비교하고, 같지 않으면 교환한다.
코드 최적화

	int i = 0;
	SKY_SERVICE_INFO *pServiceInfo[MAX_TOTAL_PROGRAM_NUM] = {NULL};

	for (i = 0; i < iProgramTotal; i++)
	{
		pServiceInfo[i] = sk_mem_malloc(sizeof(SKY_SERVICE_INFO));
		memset(pServiceInfo[i], 0, sizeof(SKY_SERVICE_INFO));
		sky_DM_Service_Get(channel[i], pServiceInfo[i]);
	}
	if (tpye == SORT_SERVICE_ID)
	{
		sk_char_service_id(pServiceInfo, iProgramTotal);

		for (i = 0; i < iProgramTotal; i++)
		{
			channel[i] = pServiceInfo[i]->id;
		}

		SendMessage(hWndGrid[PROGRAL_LIST_GRID], LMSG_SETCONTROLDATA, 0, iProgramTotal);
	}

	for (i = 0; i < iProgramTotal; i++)
	{
		if (pServiceInfo[i] != NULL)
		{
			sk_mem_free(pServiceInfo[i]);
			pServiceInfo[i] = NULL;
		}
	}

위 코드의 목적은 포인터 수조(한 수조, 수조의 모든 요소는 SKY SERVICE INFO 구조체 유형을 가리키는 포인터)pServiceInfo가 가리키는 구조체는 구조체의 특정한 구성원에 따라 배열하는 것이다.
마지막으로 pServiceInfo는 무용지물입니다. 유용한 것은 단지 채널 그룹일 뿐입니다. (pServiceInfo는 일정한 규칙을 통해 정렬한 후 ID가 채널과 대응함)
다시 skchar_service_id 함수

void sk_char_service_id(SKY_SERVICE_INFO *service_info[], int n)//    
{
	int i = 0, j = 0, iFlag = 0;
	SKY_SERVICE_INFO tmpe_service_info = {0};

	for (i = 0; i < n - 1; i++)
	{
		iFlag = 1;
		memset(&tmpe_service_info, 0, sizeof(SKY_SERVICE_INFO));
		for (j = 0; j < n - i - 1; j++)
		{
			if (str_order_service_id(service_info[j]->svid, service_info[j+1]->svid) == 0)
			{
				memcpy(&tmpe_service_info, service_info[j], sizeof(SKY_SERVICE_INFO));
				memcpy(service_info[j], service_info[j+1], sizeof(SKY_SERVICE_INFO));
				memcpy(service_info[j+1], &tmpe_service_info, sizeof(SKY_SERVICE_INFO));
				iFlag = 0;
			}
		}

		if (1 == iFlag)
		{			
			break;
		}
	}
}

여기는 간단한 거품 정렬만 사용하고if안의 교환도 최적화 공간이 크다
3번 memcpy의 과정은 바늘 서비스만info[j] 및 포인터 서비스info[j+1]가 가리키는 내용이 일치합니다. 이 3회memcpy는 대량의 cpu주기가 필요할 수 있습니다. 다른 방법을 사용하면
예를 들면 교환 서비스info[j] 및 서비스info[j+1]의 바늘값은 cpu주기를 크게 줄일 수 있습니다. 이런 방식으로 skchar_service_id 함수는 다음과 같습니다.

void sk_char_service_id(SKY_SERVICE_INFO *service_info[], int n)//    
{
	int i = 0, j = 0, iFlag = 0;
	SKY_SERVICE_INFO *ptmp_service_info = NULL;

	for (i = 0; i < n - 1; i++)
	{
		iFlag = 1;
		for (j = 0; j < n - i - 1; j++)
		{
			if (str_order_service_id(service_info[j]->svid, service_info[j+1]->svid) == 0)
			{
				ptmp_service_info	= service_info[j];
				service_info[j]		= service_info[j+1];
				service_info[j+1]	= ptmp_service_info;
				iFlag = 0;
			}
		}
		if (1 == iFlag)
		{			
			break;
		}
	}
}

또 최적화의 여지가 있다. 바로 정렬 방식을 빠른 정렬로 바꾸는 것이다.