ソート関連アルゴリズム-1
ソートコードが多すぎるため,同様に2つのブログに分けて発表する.
- #include <iostream>
- using namespace std;
-
- /*
- gap( )
- ( )
- */
- #define MAXSIZE 20
- #define MAXD 8
- typedef int ElemType;
- typedef struct node
- {
- ElemType data;
- struct node *next;
- }Node;
-
- void CreateList(Node *&nodes, int iarr[], int len) //
- {
- int loop1 = 0;
- Node *temp = NULL, *temp2 = NULL;
-
- if(nodes != NULL) free(nodes);
- nodes = (Node *)malloc(sizeof(Node));
- nodes->next = NULL;
- temp2 = nodes;
-
- for(loop1 = 0; loop1 < len ; ++loop1)
- {
- temp = NULL;
- temp = (Node *)malloc(sizeof(Node));
- temp->data = iarr[loop1];
- temp->next = temp2->next;
- temp2->next = temp;
- temp2 = temp;
- }
- }
-
- void InsertSort2(Node *&nodes) //
- {
- Node *temp = NULL, *node = NULL, *prenode = NULL, *pre = NULL;
- if(nodes == NULL || nodes->next == NULL )
- { cout<<"wrong parameter"<<endl;return ; }
- else
- { pre = nodes;
- temp = nodes->next;
-
- prenode = temp->next;
- node = temp->next;
- temp->next = NULL; // ,
-
- while(prenode != NULL)
- {
- node = prenode;
- pre = nodes;
- temp = nodes->next;
- while(temp != NULL && (node->data > temp->data)) // ,
- {
- pre = temp;
- temp = temp->next;
- }
- prenode = prenode->next;
-
- node->next = pre->next;
- pre->next = node;
- }
- }
- }
-
- void Disp(Node *nodes)
- {
- Node *temp = NULL;
- if(nodes != NULL)
- {
- temp = nodes->next;
- while(temp != NULL)
- {
- cout<<temp->data<<' ';
- temp = temp->next;
- }
- }
- cout<<endl;
- }
-
- void Disp(int iarr[], int len)
- {
- int loop1 = 0;
- while(loop1 < len)
- {
- cout<<iarr[loop1]<<' ';
- ++loop1;
- }
- cout<<endl;
- }
-
- void Disp(char iarr[][4], int len)
- {
- int loop1 = 0;
- while(loop1 < len)
- {
- cout<<iarr[loop1]<<' ';
- ++loop1;
- }
- cout<<endl;
- }
-
-
- void InsertSort(int iarr[], int len) // , ,
- {
- int loop1 = 0, loop2 = 0, loop3 = 0, temp = 0;
-
- for(loop1 = 1; loop1 < len ; ++loop1) // 1
- {
- temp = iarr[loop1];
-
- for(loop2 = 0; loop2 < loop1 && temp > iarr[loop2]; ++loop2); //
-
- loop3 = loop1;
- while(loop3 >= loop2) //
- {
- iarr[loop3] = iarr[loop3 - 1];
- --loop3;
- }
- iarr[loop2] = temp;
- }
- }
-
- void ShellSort(int iarr[], int len) // , gap, gap ,
- { // , gap , 0.
- int loop1 = 0, loop2 = 0, temp = 0, gap = 0;
-
- gap = len / 2;
- while(gap > 0)
- {
- for(loop1 = gap; loop1 < len ; ++loop1)
- {
- temp = iarr[loop1];
-
- loop2 = loop1 - gap;
- while(loop2 >= 0 && iarr[loop2] > temp) //
- {
- iarr[loop2 + gap] = iarr[loop2];
- loop2 = loop2 - gap;
- }
-
- iarr[loop2 + gap] = temp;
-
- }
- gap = gap / 2;
- }
- }
-
- void SelectSort(int iarr[], int len) // , ,
- {
- int loop1 = 0,loop2 = 0, min = 0, pos = 0; //min , pos
-
- for(loop1 = 0; loop1 < len ; ++loop1)
- { pos = loop1;
- min = iarr[loop1];
- for(loop2 = loop1 + 1; loop2 < len ; ++loop2)
- if(min > iarr[loop2])
- { min = iarr[loop2]; pos = loop2;}
-
- iarr[pos] = iarr[loop1]; //
- iarr[loop1] = min;
- }
- }
-
-
-
- void sift(int iarr[], int low, int high) // ,
- {
- int loop1 = low, loop2 = low *2 ,value = iarr[low];
-
- while(loop2 <= high)
- {
- if(loop2 < high && iarr[loop2] < iarr[loop2 + 1])
- ++loop2;
- if(value < iarr[loop2]) // iarr[low] , , loop2 , , loop2 * 2
- {
- iarr[loop1] = iarr[loop2];
- loop1 = loop2; //loop1
- loop2 = loop2 * 2;
- }else break;
- }
- iarr[loop1] = value;
- }
-
- void HeapSort(int iarr[], int len) // , ( , ), , , , 。
- { // 1 , 0
- int mid = len / 2, loop1 = 0, temp = 0;
-
- for(; mid > 0; --mid) //mid , 。
- sift(iarr,mid,len);
-
- for(loop1 = len ; loop1 > 1; --loop1)
- {
- temp = iarr[1];
- iarr[1] = iarr[loop1];
- iarr[loop1] = temp;
-
- sift(iarr,1,loop1 - 1); // , ( ) ,
- }
- }
-
-
- void sift2(int iarr[], int low, int high)
- {
- int ivar1 = low, ivar2 = low * 2, tempval = iarr[low];
-
- while(ivar2 <= high)
- {
- if(ivar2 < high && iarr[ivar2] > iarr[ivar2 + 1]) //
- ++ivar2;
-
- if(tempval > iarr[ivar2])
- {
- iarr[ivar1] = iarr[ivar2];
- ivar1 = ivar2;
- ivar2 = 2 * ivar2;
- }else break;
- }
- iarr[ivar1] = tempval;
- }
-
- void HeapSort2(int iarr[], int len) // ,
- {
- int loop1 = 0, mid = len / 2, loop2 = 0, temp = 0;
-
- for(; mid > 0; --mid)
- sift2(iarr,mid,len);
-
- for(loop2 = len ; loop2 > 1; --loop2)
- {
- temp = iarr[1];
- iarr[1] = iarr[loop2];
- iarr[loop2] = temp;
-
- sift2(iarr,1,loop2 - 1);
- }
- }
-
- bool isSmallHeap(int iarr[], int len) // , , ,
- { // , ,
- int loop1 = 0, mid = len / 2;
- bool isNOdd = false;
- if(len % 2 == 0) isNOdd = true;
- for(loop1 = 1; loop1 <= mid ; ++loop1)
- {
- if(isNOdd && loop1 == mid)
- {
- if(iarr[loop1] < iarr[2 * loop1])
- continue;
- else return false;
- }
- else
- {
- if(iarr[loop1] < iarr[2 * loop1] && iarr[loop1] < iarr[2 * loop1 + 1])
- continue;
- else return false;
- }
- }
-
- return true;
- }
-
- void BubbleSort(int iarr[], int len) // ,
- {
- int loop1 = 0, loop2 = 0, temp = 0;
- bool isExchange = false; // , , ,
- for(loop1 = 0; loop1 < len; ++loop1)
- { isExchange = false;
- for(loop2 = len -1 ; loop2 > loop1 ; --loop2) //
- {
- if(iarr[loop2] < iarr[loop2 - 1])
- {
- temp = iarr[loop2];
- iarr[loop2] = iarr[loop2 -1];
- iarr[loop2 - 1] = temp;
- isExchange = true;
- }
- }
- if(!isExchange) return ;
- }
- }
-
- void DBubble(int iarr[], int len) // , ,
-
- {
- int loop1 = 0, mid = len / 2, loop2 = 0,temp = 0;
-
- bool isExchange = false;
- for(loop1 = 0; loop1 < mid; )
- { isExchange = false;
- for(loop2 = len -1 - loop1; loop2 > loop1; --loop2) //
- {
- if(iarr[loop2] < iarr[loop2 - 1])
- {
- temp = iarr[loop2];
- iarr[loop2] = iarr[loop2 - 1];
- iarr[loop2 - 1] = temp;
- isExchange = true;
- }
- }
- ++loop1; // ++ loop1 ,
- if(isExchange && loop1 < mid) // loop1
- {
- for(loop2 = loop1; loop2 < len - loop1; ++loop2) // , loop2 < len - loop1,
- {
- if(iarr[loop2] > iarr[loop2 + 1])
- {
- temp = iarr[loop2];
- iarr[loop2] = iarr[loop2 + 1];
- iarr[loop2 + 1] = temp;
- }
- }
- }else return ;
- }
- }
-
-
- void DBubble2(int iarr[], int len) // , exchange==1,
- {
- int loop1 = 0, ivar = 0, temp = 0;
- int exchange = 1;
-
- while(exchange == 1)
- {
- exchange = 0;
- for(loop1 = len -1 -ivar; loop1 > ivar; --loop1)
- {
- if(iarr[loop1] < iarr[loop1 - 1])
- {
- temp = iarr[loop1];
- iarr[loop1] = iarr[loop1 - 1];
- iarr[loop1 - 1] = temp;
- exchange = 1;
- }
- }
- ++ivar;
- if(exchange == 1)
- for(loop1 = ivar; loop1 < len - ivar; ++loop1)
- {
- if(iarr[loop1] > iarr[loop1 + 1])
- {
- temp = iarr[loop1];
- iarr[loop1] = iarr[loop1 + 1];
- iarr[loop1 + 1] = temp;
- }
- }
- }
- }
-
-
- void QuickSort(int iarr[], int begin, int end) // , , , ,
- { // , , , ,
- int temp = iarr[begin], loop1 = begin, loop2 = end - 1; // , 。
- // cout<<"loop1 : "<<loop1<<" loop2 : "<<loop2<<" begin : "<<begin<<" end :"<<end<<endl;
- if(begin >= end) return;
-
- while(loop1 < loop2)
- {
- while(loop1 < loop2 && iarr[loop2] > temp)
- --loop2;
- if(loop1 < loop2) // , --loop2 loop2 < loop1
- { iarr[loop1] = iarr[loop2];
- ++loop1; // ++ ,
- }
-
- while(loop1 < loop2 && iarr[loop1] < temp)
- ++loop1;
- if(loop1 < loop2)
- {
- iarr[loop2] = iarr[loop1];
- --loop2;
- }
- }
-
- cout<<"loop1 : "<<loop1<<" loop2 : "<<loop2<<endl;
- iarr[loop1] = temp;
- QuickSort(iarr,begin, loop1 );
- QuickSort(iarr,loop1 + 1, end );
- }
-
- void QuickSort2(int iarr[], int begin, int end) // ,
- {
- struct
- {
- int begin, end;
- }st[MAXSIZE],temp;
- int front = -1, rear = -1, ivar1 = 0, ivar2 = 0, tempval = 0;
-
- ++rear;
- st[rear].begin = begin;
- st[rear].end = end;
-
- while(front < rear)
- {
- ++front;
- temp = st[front];
-
- ivar1 = temp.begin;
- ivar2 = temp.end - 1;
-
- if(ivar1 == ivar2) continue; // , ,
-
- tempval = iarr[ivar1]; // while , ivar1
- while(ivar1 < ivar2)
- {
- // cout <<"ivar1 "<<ivar1<<" ivar2: "<<ivar2<<endl;
- while(ivar2 > ivar1 && iarr[ivar2] > tempval)
- --ivar2;
- if(ivar2 > ivar1)
- {
- iarr[ivar1] = iarr[ivar2];
- ++ivar1;
- }
- // cout <<" iva r1 "<<ivar1<<" ivar2: "<<ivar2<<endl;
- while(ivar2 > ivar1 && iarr[ivar1] < tempval)
- ++ivar1;
- if(ivar2 > ivar1)
- {
- iarr[ivar2] = iarr[ivar1];
- --ivar2;
- }
- // cout <<" ivar1 "<<ivar1<<" ivar2: "<<ivar2<<endl;
- }
- cout<<"ivar1 : "<<ivar1<<" ivar2 : "<<ivar2<<endl; // ivar2 -1?? ivar2 = temp.end - 1; begin end , loop1 loop2
- iarr[ivar1] = tempval; // ,
- if(ivar1 == ivar2) // , ivar1 == ivar2 , (ivar1 == ivar2),
- {
- ++rear;
- st[rear].begin = temp.begin;
- st[rear].end = ivar1;
- ++rear;
- st[rear].begin = ivar1 + 1;
- st[rear].end = temp.end;
- }
- }
- }
- /*
- void Partition(int iarr[], int begin, int end)
- {// cout<<"begin : "<<begin<<" end :"<<end<<endl;
- int temp = 0, ivar1 = begin, ivar2 = end , mid = (ivar1 + ivar2) / 2 , tempval = 0;
- if(ivar1 >= ivar2) return;
- temp = iarr[mid];
-
- while(ivar1 < ivar2)
- {
- while(ivar2 > ivar1 && iarr[ivar2] >= temp)
- --ivar2;
- while(ivar2 > ivar1 && iarr[ivar1] <= temp)
- ++ivar1;
- if(ivar1 < ivar2)
- {
- tempval = iarr[ivar1];
- iarr[ivar1] = iarr[ivar2];
- iarr[ivar2] = tempval;
-
- }
- }Disp(iarr,12);
-
- iarr[mid] = iarr[ivar1];
- iarr[ivar1] = temp;
- // system("pause");
- Partition(iarr,begin,ivar1 -1);
- Partition(iarr,ivar1 + 1, end);
- }
-
- void QuickSortX(int iarr[], int begin, int end)
- {
- int pos = 0;
- Partition(iarr,begin, end);
- if(begin < pos -1)
- QuickSortX(iarr,begin,pos);
- if(pos + 1 < end - 1)
- QuickSortX(iarr,pos + 1,end);
- }
- */
-
- void Merge(int iarr[], int begin, int mid, int end) // , ( )
- {
- int iarr2[MAXSIZE], loop1 = 0, tempmid = 0, count = 0;
-
- for(loop1 = 0, tempmid = mid + 1; loop1 <= mid && tempmid <= end; )
- {
- if(iarr[loop1] > iarr[tempmid])
- {
- iarr2[count] = iarr[tempmid];
- ++tempmid;
- ++count;
- }else if(iarr[loop1] < iarr[tempmid])
- {
- iarr2[count] = iarr[loop1];
- ++loop1;
- ++count;
- }else
- {
- iarr2[count] = iarr[loop1];
- ++loop1;
- ++count;
- iarr2[count] = iarr[tempmid];
- ++tempmid;
- ++count;
- }
- }
- if(loop1 > mid)
- {
- while(tempmid <= end)
- {
- iarr2[count] = iarr[tempmid];
- ++count;
- ++tempmid;
- }
- }
- if(tempmid > end)
- {
- while(loop1 <= mid)
- {
- iarr2[count] = iarr[loop1];
- ++count;
- ++loop1;
- }
- }
- for(loop1 = 0; loop1 <= end; ++loop1)
- iarr[loop1] = iarr2[loop1];
- }
-
- void MergePass(int iarr[], int end, int length) // length ,
- {
- int pos = 0;
- for(pos = 0; pos + 2 * length -1 <= end; pos = pos + 2 * length)
- Merge(iarr,pos,pos + length - 1, pos + 2 * length - 1);
- if(pos + length - 1 < end)
- Merge(iarr,pos, pos + length -1 , end);
- }
-
- void MergeSort(int iarr[], int len) // , 1 ,
- {
- int length = 1;
- for(length = 1; length < len ; length *= 2)
- MergePass(iarr,len,length);
- }
-
- typedef struct rnode
- {
- char data[MAXD];
- struct rnode *next;
- }RecType;
-
- void RadixSort(char carr[][4], int len, int weishu) ///
- {
- int loop1 = 0, num = 0,count = 0, loop2 = 0;
- RecType head[MAXSIZE], *tail[MAXSIZE] = {NULL}, *temp = NULL;
-
- for(count = weishu -1;count >= 0; --count)
- {
- for(loop1 = 0; loop1 < MAXSIZE; ++loop1)
- {
- tail[loop1] = NULL;
- head[loop1].next = NULL;
- }
-
- for(loop1 = 0; loop1 < len; ++loop1) // ,
- {
- num = int(carr[loop1][count] - '0');
- temp = (RecType *)malloc(sizeof(RecType));
- strcpy(temp->data, carr[loop1]);
- temp->next = NULL;
- if(tail[num] == NULL)
- {
- tail[num] = temp;
- head[num].next = tail[num];
- }else
- {
- temp->next = tail[num]->next;
- tail[num]->next = temp;
- tail[num] = temp;
- }
- }
- loop2 = 0;
- for(loop1 = 0; loop1 < len; ++loop1) //
- {
- if(tail[loop1] == NULL)
- {cout<<"loop1 "<<loop1<<endl; }
- else
- {
- temp = head[loop1].next;
- while(temp != NULL)
- {
- strcpy(carr[loop2++],temp->data);
- temp = temp->next;
- }
- }
- }
-
- for(loop1 = 0; loop1 <len; ++loop1)
- cout<<carr[loop1]<<' ';
- cout<<endl;
- }
- }