... notes by A.Kamburelis
... will be expanded and translated


// Πίνακες Δομών

We shall use the structure:

struct Item { int key; int data };

key: may be AM, ADT, AFM, IKA...
data: may be Name, Address etc

We define array externally.
Exercise: hide it, in main()

#define N 20 // μήκος του πίνακα

struct Item pin[N];


First, fill pin by random values and show it on the screen

#include <stdio.h>
#include <stdlib.h> // for random numbers rand()
#define N 20 // μήκος του πίνακα

struct Item { int key; int data }; // new type

struct Item pin[N]; // external array pin

void fill(){ int i; 
  for(i=0;i<N;i++){ 
    pin[i].key  = rand()%1000; // fill by random keys, modulo 1000
    pin[i].data = i;
  }
}

void show(){ int i; 
  for(i=0;i<N;i++)
    printf( "%8d %8d %8d \n", i, pin[i].key, pin[i].data );
}

main(){
  fill(); show();
}


 
Searching for minimal key

First try:

  min = pin[0].key;
  for ( i=0; i<N; i++ )
    if (pin[i].key<min) min = pin[i].key;

We have min value. But we don’t know WHERE it is!

Second try:

  mi = 0;
  for ( i=0; i<N; i++ )
    if (pin[i].key<pin[mi].key) mi = i;

Now we have the index (mi) of the minimal key!
To find its value, just set: min = pin[mi].key;


*Sorting

Putting array into ascending key-order.

Simple sorting methods:

Bubble sort: forget it! Never use it!
Insertion sort: not very efficient.
Selection sort: a nice, simple method.

Sophisticated methods:

Quick sort: this is a "strange pearl" in sorting algorithms.

HeapSort: the BEST one! Recommended!
It works like Selection sort, but it uses Heap structure
for finding minimal key.

Merge sort: very good, but needs additional memory.


We will programm Selection sort (details in Lab).

void SelectionSort(){ int i,j,mi; struct Item help;

  for(i=0;i<N-1;i++){ // why N-1 ?

    // first step: find minimal key position
    mi := i;
    for(j=i;j<N;j++)
      if(pin[j].key<pin[mi].key) mi=j;

    // second step: swap pin[i] with pin[mi]
    help=pin[i]; pin[i]=pin[mi]; pin[mi]=help;
  }
}


Now use:

main(){
  fill(); show();
  SelectionSort();
  show();
}



Using build-in qsort function (from <stdlib.h>). Two steps.

First, write a \b comparison\ function

int MyCompare (const void *a, const void *b){
  return ((struct Item *)a)->key  - // minus
         ((struct Item *)b)->key;
}

Second, call qsort:
  
  qsort ( pin, N, sizeof(struct Item), MyCompare );


Details in Lab...