疑問 - c語言merge sort的問題

[cara4bear]

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 8; //暫設大小為8

void merge(int *data[], int length);
void mergesort(int *data[], int left, int mid, int right);

void main(void)
{
int data[] = {5,1,7,50,10,4,80,33};
int i = 0;
srand(time(NULL));
int length = SIZE;
printf("陣列大小:%d \n", length);
printf("原陣列:");
for(i = 0; i < length; i ++){//亂數產生放入陣列中
//data[i] = rand();
printf("%d ", data[i]);
}

merge(*data, length);
printf("\n排列後之陣列:");
for(i = 0; i < length; i ++){
printf("%d ", data[i]);
}
system("pause");
return(0);
}



void merge(int *data[], int length)
{
int count = 0, size = 1;//分割用
int left = 0, right = 0, mid = 0; //指標用
while(count < 5){
while(1){
mid = (left + size)-1;
right = (mid + size);
if(length <= right){
right = length - 1;
if(right <= mid){
break;}
}

mergesort(*data, left, mid, right);
left = right + 1;
printf("\n%d %d", right, mid);
}
count += 1;
size *= 2;
}

}

void mergesort(int *data[], int left, int mid, int right)
{
int temp[] = {};
int i = 0, j = left, k = left;

while(j<=mid){
temp[i] = *data[j];
i++;
j++;
}
i = 0;
while(j <= right){
if(temp[i] <= *data[j]){
*data[k] = temp[i];
k ++;
i ++;
}else{
*data[k] = *data[j];
k ++;
j ++;
}
}
while (k < j){
*data[k] = temp[i];
k = k+1; i = i+1;
}
}


想寫一個bottom-up的merge sort
但卻無法執行
應該是mergesort的副程式有問題吧
可是卻不知道到底問題出在哪> <

想請各位高手幫小女解惑

拜託各位大哥大姊了

[pedrowong]

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 8; //暫設大小為8

void merge(int *data[], int length);
void mergesort(int *data[], int left, int mid, int right);

void main(void)
{
int data[] = {5,1,7,50,10,4,80,33};
int i = 0;
int length = SIZE;

srand(time(NULL));

printf("陣列大小:%d \n", length);
printf("原陣列:");
for(i = 0; i < length; i ++){//亂數產生放入陣列中
//data[i] = rand();
printf("%d ", data[i]);
}

merge(&data, length);
printf("\n排列後之陣列:");
for(i = 0; i < length; i ++){
printf("%d ", data[i]);
}
system("pause");
return;
}



void merge(int *data[], int length)
{
int count = 0, size = 1;//分割用
int left = 0, right = 0, mid = 0; //指標用

while(count < 5){
while(1){
mid = (left + size)-1;
right = (mid + size);
if(length <= right){
right = length - 1;
if(right <= mid){break;}
}

mergesort(data, left, mid, right);
left = right + 1;
printf("\n%d %d", right, mid);
}
count += 1;
size *= 2;
}

}

void mergesort(int *data[], int left, int mid, int right)
{
int temp[8];
int i = 0, j = left, k = left;

while(j<=mid){
temp[i] = data[j];
i++;
j++;
}
i = 0;
while(j <= right){
if(temp[i] <= data[j]){
data[k] = temp[i];
k ++;
i ++;
}else{
data[k] = data[j];
k ++;
j ++;
}
}
while (k < j){
data[k] = temp[i];
k = k+1; i = i+1;
}
}

[getter]

錯誤一：void mergesort(int *data[], int left, int mid, int right)

當 void mergesort(int *data[], int left, int mid, int right)
有 * 號指標變數不宜同時使用有 [] 號，某些編譯器會出錯。

* 號的作用與 & 的作用相當都只做記憶體位址的轉換與呼叫 ...

這樣就能直接存取上層的變數了不然一般的

void mergesort(int data[],int left, int mid, int right)

意旨開個專櫃去接受外來的資料，當資料改變時也是只有這個專櫃
改變而已，並不會影響的上層宣告 data。動來動去都是 () 內的
宣告的變數。

若是要直接存取上層的變數的資料，就要透過 * 號指標變數，
其實指標變數的作用就是直接存取上層宣告 data，這是就能存取
原先的變數內容了。

void mergesort(int *data,int left, int mid, int right)


錯誤二 {} 內的 *

void mergesort(int *data, int left, int mid, int right)
{ 
int temp[] = {};
int i = 0, j = left, k = left;

while(j<=mid){
temp[i] = *data[j];
i++;
j++;
}

i = 0;
while(j <= right){
if(temp[i] <= *data[j]){
*data[k] = temp[i];
k ++;
i ++;
}else{
*data[k] = *data[j];
k ++;
j ++;
}
}

while (k < j){
*data[k] = temp[i];
k = k+1; i = i+1; 
}

}

當副程式的宣告 void mergesort(int *data, int left, int mid, int right)
已經做好了銜接時，就可以直接依照原來的陣列語法直接操作資料的演算，無須
在加 * 號了，若要使用 * 號的話要以指標變數的對應操作的方式進行處理如下

data[0] 對應到 *data 或 *(data+0)
data[1] 對應到 *(data+1)
data[2] 對應到 *(data+2)



錯誤三 mergesort 副程式中的 int temp[] = {};

void mergesort(int *data, int left, int mid, int right)
{ 
int temp[] = {};
int i = 0, j = left, k = left;

while(j<=mid){
temp[i] = data[j];
i++;
j++;
}

i = 0;
while(j <= right){
if(temp[i] <= data[j]){
data[k] = temp[i];
k ++;
i ++;
}else{
data[k] =data[j];
k ++;
j ++;
}
}

while (k < j){
data[k] = temp[i];
k = k+1; i = i+1; 
}

}

這樣的陣列宣告是錯誤的，會生一個邏輯的錯誤，可能變成只有
1 個長度的陣列 ... 當後方程式語法使用是大於 1 個長度的陣
列，就會發生錯誤了，宣告陣列一定要有大小，不然就由資料大
小做陣列的大小做調整。當然某些編譯器會當作是語法的錯誤而
不執行。


錯誤四 merge、mergesort 副程式可能有種邏輯錯誤

依據 merge、mergesort 的程式來看，其程式結果可能是整個排序
的結果可能是兩兩一組的前後對換而已，如下

排序前 5, 1, 7,50,10, 4,80,33
排序後 1, 5, 7,50, 4,10,33,80

若是要做到這種排序效果可以將程式化簡如下：

void merge(int *data, int length)
{
int i; 
for(i=0;i<length;i+=2){
mergesort(data, i, i+1);
printf("\n right=%d ,mid=%d", i+1, i);} 
}

void mergesort(int *data, int mid, int right)
{ 
int temp;
if(data[mid] > data[right]){
temp = data[mid];
data[mid] = data[right];
data[right] = temp;} 
}

可以進一步的合併成

void mergesort(int *data, int length)
{
int i,temp;
for(i=0;i<length;i+=2){
if(data[i] > data[i+1]){
temp = data[i];
data[i] = data[i+1];
data[i+1] = temp;} 
printf("\n right=%d ,mid=%d", i+1, i);} 
}

最後如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 8; //暫設大小為8

void mergesort(int *data, int length);

void main(void)
{
int data[] = {5,1,7,50,10,4,80,33};
int i = 0;
int length = SIZE; 

printf("陣列大小: %d \n",length);
printf("原陣列:");

for(i = 0; i < length; i ++){//亂數產生放入陣列中 
//data[i] = rand();
printf("%d ", data[i]);}

mergesort(data, length);

printf("\n排列後之陣列:");
for(i = 0; i < length; i ++){ 
printf("%d ", data[i]);}

printf("\n\n");
system("pause");
}


void mergesort(int *data, int length)
{
int i,temp;
for(i=0;i<length;i+=2){
if(data[i] > data[i+1]){
temp = data[i];
data[i] = data[i+1];
data[i+1] = temp;} 
printf("\n right=%d ,mid=%d", i+1, i);} 
}

[cwvdavid]

已經是斷頭文了...