リンクリストをソートする

通常のソート方法

隣接のノードを比較し、どちらかより大きいな数字が存在したら、お互いの数値を交換します。
(ノード数-1)の回数でループが実施されるため、無駄な処理が発生します。

sort.c

# include <stdio.h>
# include <stdlib.h>

//node declaration and pointer declaration
struct node{
  int data;
  struct node *link;
} *start, *visit;

//function declaration
void displaylist();
void getdata();
void append(struct node **, int);
int count(struct node *);
void selection_sort(int);

void main(){
  //declare value to get length of list
  int n;
  
  //create list
  getdata();
  
  //display list
  printf("Linked list before sorting: \n");
  displaylist();
  
  //get length of list
  n = count(start);

  //sort the list
  selection_sort(n);
  
  //display list
  printf("Linked list after selection sorting: \n");
  displaylist();  
}

//sort linked list(ascend order)
void selection_sort(int num){
  //declare variable for loop counter and value exchange
  int i, temp;
  //declare pointer to be used to set different starting point for loop through list
  struct node *t;
  
  //set starting point to top of list
  t = start;
  
  //loop for the number of length of list - 1
  for(i = 0; i<num-1; i++){
    //set locator pointer to a starting point
    visit = t;
    
    //loop through list
    while(visit->link != NULL){
      //if current value is bigger than the next one, exchange value of each node
      if(visit->data > (visit->link)->data){
         //hold current value of node
         temp = visit->data;
         //insert value from next node into current node
         visit->data = (visit->link)->data;
         //insert value of current node to the next node
         (visit->link)->data = temp;
      }
      //go to next node
      visit = visit->link;
    }
    
    //set starting point to the next node
    t = t->link;
    
  }
  
}

//get length of list
int count(struct node *q){
  //declare variable to store number of nodes
  int c = 0;
  
  //loop through list
  while(q!=NULL){
    //add to count
    c++;
    //go to next node
    q = q->link;
  }
  
  return c;
}

//get value for nodes to be added to list.
void getdata(){
  //declare variable to get inputed value
  int val;
  //declare variable to get yes or no answer. declare variable to clear stdin
  int ch, cs;
  //declare pointer to new list
  struct node *new;
  
  //set pointer to empty
  new = NULL;
  
  //loop for adding nodes to list
  do{
    //ask for value of node
    printf("Enter a value: ");
    scanf("%d", &val);

    //clear stdin. if this is not done, newline will be read into ch.
    while( (cs=getchar()) != '\n' && cs!= EOF);
    
    //append node to new list
    append(&new, val);
    
    //ask if want to add more nodes
    printf("Any more nodes(Y/N): ");
    //get one character
    ch = getchar();
  }while(ch == 'y' || ch == 'Y');
  
  //set pointer to new list
  start = new;
}

//append node to list
void append(struct node **q, int num){
  struct node *temp, *r;
  
  //create new node
  r = malloc(sizeof(struct node));
  //set value of new node
  r->data = num;
  //set link of new node to null
  r->link = NULL;
  
  //if list is empty
  if(*q==NULL){
    //set pointer to new node
    *q = r;
  }else{
    //set locator pointer to top of list
    temp = *q;
    
    //go to last node
    while(temp->link != NULL){
      temp = temp->link;
    }
    
    //set link of last node to new node
    temp->link = r;
    
  }
}

//display node in list
void displaylist(){
  struct node *q;
  
  //set locator pointer to list
  q = start;
  
  //loop through list
  while(q != NULL){
    //print data
    printf("%d\n",q->data);
    //go to next node
    q = q->link;
  }
}

バブルソートの方法

隣接のノードを比較し、どちらかより大きいな数字が存在したら、お互いの数値を交換します。
数値の交換が行われなければ、ループは最後まで実施せず処理が完了します。

bubblesort.c

# include <stdio.h>
# include <stdlib.h>

//node declaration and pointer declaration
struct node{
  int data;
  struct node *link;
} *start, *visit;

//function declaration
void displaylist();
void getdata();
void append(struct node **, int);
int count(struct node *);
void bubble_sort(int);

void main(){
  //declare value to get length of list
  int n;
    
  //create list
  getdata();
  
  //display list
  printf("Linked list before sorting:\n");
  displaylist();
  
  //get length of list
  n = count(start);
  
  //sort the list
  bubble_sort(n);
  
  //display list
  printf("Linked list after bubble sorting:\n");
  displaylist();
  
}

//bubble sort
void bubble_sort(int num){
  //declare variable for loop and exchange value
  int i, temp;
  //declare variable to count numbers of swipe
  int c;
  
  //loop 
  for(i=0; i<num-1; i++){
    //set locator point to the front of list
    visit = start;
    //set counter to zero
    c = 0; 
  
    //loop until second last node
    while(visit->link!=NULL){
      //if data of current node is bigger than the next node, exchange value
      if(visit->data > (visit->link)->data){
        //hold value of current node
        temp = visit->data;
        //set value of next node to current node
        visit->data = (visit->link)->data;
        //set value of next node with new value
        (visit->link)->data = temp;
        //add to counter
        c++;
      }
      //go to next node
      visit = visit->link;
    }
    
    //if no swap occurs, break out of loop
    if(c==0){
      break;
    }
  
  }
}

//get length of list
int count(struct node *q){
  //declare variable to store number of nodes
  int c = 0;
  
  //loop through list
  while(q!=NULL){
    //add to count
    c++;
    //go to next node
    q = q->link;
  }
  
  return c;
}

//get value for nodes to be added to list.
void getdata(){
  //declare variable to get inputed value
  int val;
  //declare variable to get yes or no answer. declare variable to clear stdin
  int ch, cs;
  //declare pointer to new list
  struct node *new;
  
  //set pointer to empty
  new = NULL;
  
  //loop for adding nodes to list
  do{
    //ask for value of node
    printf("Enter a value: ");
    scanf("%d", &val);

    //clear stdin. if this is not done, newline will be read into ch.
    while( (cs=getchar()) != '\n' && cs!= EOF);
    
    //append node to new list
    append(&new, val);
    
    //ask if want to add more nodes
    printf("Any more nodes(Y/N): ");
    //get one character
    ch = getchar();
  }while(ch == 'y' || ch == 'Y');
  
  //set pointer to new list
  start = new;
}

//append node to list
void append(struct node **q, int num){
  struct node *temp, *r;
  
  //create new node
  r = malloc(sizeof(struct node));
  //set value of new node
  r->data = num;
  //set link of new node to null
  r->link = NULL;
  
  //if list is empty
  if(*q==NULL){
    //set pointer to new node
    *q = r;
  }else{
    //set locator pointer to top of list
    temp = *q;
    
    //go to last node
    while(temp->link != NULL){
      temp = temp->link;
    }
    
    //set link of last node to new node
    temp->link = r;
    
  }
}

//display node in list
void displaylist(){
  struct node *q;
  
  //set locator pointer to list
  q = start;
  
  //loop through list
  while(q != NULL){
    //print data
    printf("%d\n",q->data);
    //go to next node
    q = q->link;
  }
}