Lecture 17, ECE264, Spring 2012, Prof. Lu

Peachanok Lertkajornkitti Lecture Fri 9Mar Lecture 17

/*Stats on the exam 1 mean: 7.10/14

Q1: 2.49/5 (Outcome 1,FILE, passed if >= 2.5)

Q2: 3.10/6 (OUtcome 2,STRUCT, passed if >= 2.5)

Q3: 1.35/3

Next exam test OUTCOME 3 THIRD EXAM test OUTCOME 1&2 (Make up exam)

SORTING -Insertion sort -Bubble sort -Selection sort

-Merge sort -Quick sort

SELECTION SORT -find min value -swap with first position -repeats until end of array (advance position every time)

i.e 42| 19 73 32 4

4 19 73 32 42 (Swap 4 and 42)

4 19 73 32 42 (Looking at values to the right of 19, 19 is the smallest)

4 19 32 73 42 (Looking at the values to the right of 73, 32 is the smallest, swap 32 with 73)

4 19 32 42 73 (Looking at the values to the right of 73, 42 is the smallest, swap)

• /

//EXERCISE 5

1. include<stdio.h>
2. include<stdlib.h>

typedef struct{ int length; int *data; }IntArray

IntArray *IntArray_create //incomplete but similar to Maze_create

IntArray IntArray_destroy //remember to destroy every time you create

IntArray *IntArray_load(char *file) { FILE *f = fopen(argv[1],"r"); if(f == NULL) { return NULL; }

const int BUFFER_LENGTH = 80; char buffer[BUFFER_LENGTH); int lineNumber = 0; while(fgets(buffer,BUFFER_LENGTH,f) != NULL){ array->data[lineNumber++] = strtol(buffer,NULL,10);

//or fscanf(f, "%d", array->data[lineNumber++]; }

fclose(f); return array; }

int main(int argc, char *argv[]) { if(argc != 2){ return EXIT_FAILURE; }

intArray *array = IntArray_load(argv[1]); if(array == NULL){ return EXIT_FAILURE;

//Sort IntArray_sort(array);

}

int IntArray_findMin(IntArray *array,int offset) { int i; int min = array->data[offset]; int minIndex; for (i = offset;1<array->length;i++){ if(array->data[i] < min) { min = array->data[i]; minIndex = i; } } return minIndex; }

void IntArray_swap(IntArray *array, int a,int b) { int tmp = array->data[a]; array->data[a] = array->data[b]; array->data[b] = tmp; } //SORTING void IntArray_sort(IntArray *array) { int i; for(i=0;i<array->length - 1; i++){ int minIndex = IntArray_findMin(array,i); IntArray_swap(array,i,minIndex); } }

Huayi Guo section-1 Professor Niklas 0309

/*

 Lecture309
 
 ex5
 implementing sorting
  
   Insertion sorting
   Bubble sorting
   Selection sorting
   Merge sorting
   Quick sorting
   

linear search: takes N times bineary search: takes log(N) times

• /

IniArray *INtArray_load(char *file)
{
   

  const int BUFEER =80;
  char buffer[BUFFER_LENGTH];
  int lineN =0 ;
  while(fgets(buffer, BUFFER, f) != NULL){
    lineN++;
  }
  
  rewind(f);
  //creat the structure here;
  
  lineN =0 ;
  while(fgets(buffer, BUFFER, f) != NULL){
    array->data[lineN++] = strtol(buffer,NULL 10);
  }
  
  fclose(f);
  
  return array;
}

===================

Kevin Tan(0023987592), section#2 notes 03/08

selection sorting -> ordering values ( 9 6 3 1 7 8 4 5 0)

first step: put smallest at beginning

for (i=0;i<(len-1);i++) {

 k=i;
 for(j=i+1;j<len;j++)
 {
   if(arr[k]>arr[j])
   {
     k=j;
   }
 }
 if(k!=i)
 {
   swap(&arr[i],&arr[k])
 }

}

void swap(int *a,int *b) {

 int c=*a;
 *a=*b;
 *b=c;

}

Back to ECE264, Spring 2012, Prof. Lu