Δομές άσκηση

[kkarampoulas]

ΓΕΙΑ σε όλους.Έχω μία εργασία στο μάθημα Δόμες Δεδομένων που πρέπει να παραδώσω μέχρι την δευτέρα.Είναι το μόνο μάθημα που χρωστάω γι΄αυτό ζητω την βοήθειά σας.ΟΠΟΙΟΣ μπορεί ας βοηθήσει.ΕΥΧΑΡΙΣΤΩ!!!!

[kkarampoulas]

το πρόβλημα:

Υλοποιήστε τους ακόλουθους αλγορίθμους:

- Bubblesort

- InsertionSort

- Quicksort με στοιχείο διαχωρισμού το αριστερότερο στοιχείο του πίνακα

- Quicksort με στοιχείο διαχωρισμού τυχαίο στοιχείο του πίνακα

- Quicksort με στοιχείο διαχωρισμού τυχαίο στοιχείο του πίνακα, ο οποίος καλεί την InsertionSort όταν το μέγεθος του υποπίνακα γίνει <= INSERTIONFACTOR (π.χ 10).

Όλοι οι αλγόριθμοι θα μετρούν: i) το πλήθος των συγκρίσεων και ii) το πλήθος των αντιμεταθέσεων.

Στη main() θα εμφανίζεται το ακόλουθο μενού:

1. Δημιουργία Πίνακα

2. Σώσιμο Πίνακα σε Αρχείο

3. Διάβασμα Πίνακα από Αρχείο

4. Εμφάνιση Πίνακα

5. BubbleSort

6. InsertionSort

7. QuickSort1

8. QuickSort2

9. QuickSort3

0. Έξοδος

 

Η επιλογή 1 θα δημιουργεί έναν πίνακα ακεραίων δυναμικά (ζητώντας το επιθυμητό μέγεθος από τον χρήστη). Για την αρχικοποίηση των τιμών του πίνακα θα υπάρχουν 2 επιλογές: a) αταξινόμητος (γεμίζοντας κάθε κελί με μία τιμή random [0..10]), σχεδόν ταξινομημένος, για την υλοποίηση αρχικά θα γεμίζει ο πίνακας με διαδοχικές τιμές 1,2,3,..,Ν και κατόπιν θα διαλέγονται Ν/PAIRFACTOR πχ. Ν/100 τυχαία ζευγάρια κελιών τα οποία και θα ανταλλάσουν τιμές.

 

Η επιλογή 2 θα σώζει τον τρέχον πίνακα σε ένα προκαθορισμένο αρχείο (το όνομα θα είναι global μεταβλητή), ενώ η 3 θα διαβάζει τον πίνακα από το προκαθορισμένο αρχείο. Η 4 θα εμφανίζει τον πίνακα, ενώ οι επιλογές 5-9 θα καλούν τις αντίστοιχες μεθόδους ταξινόμησης

 

Πείραμα: Δημιουργήστε πίνακες μεγέθους 1000, 10000, 100000 και με τους δύο τρόπους αρχικοποίησης. Τρέξτε τους αλγορίθμους και πάρτε τις αντίστοιχες τιμές για τις συγκρίσεις που εκτελούν. Βεβαιωθείτε ότι όλοι οι αλγόριθμοι τρέχουν για τον ίδιο πίνακα (μεγέθους 1000, 10000, 100000). Σχεδιάστε σε γραφήματα τις μετρήσεις που πήρατε. Στον άξονα x θα έχετε το μέγεθος του πίνακα και στον y το μετρούμενο μέγεθος. Τι παρατηρείτε όσον αφορά τη συμπεριφορά των αλγορίθμων ; Ποιον αλγόριθμο θα επιλέγατε αν ο πίνακας είναι πλήρως αταξινόμητος, ποιoν αν είναι σχεδόν ταξινομημένος και ποιον αν δεν ξέρουμε τη μορφή του;

Πειραματιστείτε με διαφορετικές τιμές για τα INSERTIONFACTOR και PAIRFACTOR ώστε να τεκμηριώσετε καλύτερα την απάντησή σας.

[kkarampoulas]

ο κώδικας (πρέπει να συμπληρωθουν τα ********************)

 

#include <stdio.h>

#include <time.h>

#include <stdlib.h>

 

#define PAIRFACTOR 100 //used for almost sorted array: number of pairs to be swapped=dim/PAIRFACTOR

#define INSERTIONFACTOR 10 //used in Quicksort3: when array <=INSERTIONFACTOR insertionSort is called

 

char fname[40] = "data.txt"; //filename

 

 

void swap(int *a, int *{

int temp;

 

temp=*a;

*a=*b;

*b=temp;

}

 

 

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

output: A sorted in increasing order

number of comparissons between array elements

*/

void bubblesort(int *A,int left, int right, int *comps){

 

/*********************************************/

}

 

 

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

output: A sorted in increasing order

number of comparissons between array elements

*/

void insertionsort(int *A, int left, int right, int *comps){

 

/*****************************************/

}

 

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

pivotIndex: the position of pivot element

output: A such that pivot is in its correct (sorted) position,

the elements left of the pivot are smaller or equal to the pivot

the elements right of the pivot are greater than the pivot

returns pivot's position

*/

int partition (int *A, int left, int right, int pivotIndex, int *comps){

 

/*****************************************/

 

}

 

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

mode 1: pivot=left

mode 2: pivot=random

mode 3: pivot=random + insertionSort

output: A sorted in increasing order

number of comparissons between array elements

*/

void quicksort(int *A, int left, int right, int mode, int *comps){

 

/**********************************/

[bokarinho]

Και να σκεφτείς ότι εμάς αυτή την άσκηση θα την θεωρούσαν γελοία και ούτε στον προγραμματισμό δεν θα την έβαζαν.

 

Να μία saveArray - loadArray:

 

>
int saveArray(int *A, int dim)
{
FILE *fileptr = NULL;
static int Index = 0;
if((fileptr = fopen(fname, "wt")) == NULL)
{
	fprintf(stderr, "Error: Can open \"%s\"\n", fname);
	return -1;
}
else
{
	for(Index = 0; Index < dim; Index++)
		if(fprintf(fileptr,"Array[%d] = %d\n", Index, A[index]) < 0)
			break;
}
/* Close file. */
fclose(fileptr);
return Index == dim ? 1 : 0;
}

int loadArray(int **A, int *dim)
{
FILE *fileptr = NULL;
int d = 0;
static int Index = 0;
if((fileptr = fopen(fname, "rt")) == NULL)
{
	fprintf(stderr, "Error: Can open \"%s\"\n", fname);
	return -1;
}
else
{
	while(1)
	{

		if(fscanf(fileptr,"Array[%d] = %d\n", &(*dim), &(*(*A + d++))) != 2)
			break;
	}
	*dim += 1;
	fclose(fileptr);
	return 0;
}
}

[kkarampoulas]

ΕΥΧΑΡΙΣΤΩ ρε μεγαλε!Τι να σ πω εμενα με παιδευουν λιγο αυτα ρε συ αλλα που θα μου παει....

[kkarampoulas]

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

output: A sorted in increasing order

number of comparissons between array elements

*/

void bubblesort(int *A,int left, int right, int *comps){

 

/*********************************************/

}

 

 

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

output: A sorted in increasing order

number of comparissons between array elements

*/

void insertionsort(int *A, int left, int right, int *comps){

 

/*****************************************/

}

 

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

pivotIndex: the position of pivot element

output: A such that pivot is in its correct (sorted) position,

the elements left of the pivot are smaller or equal to the pivot

the elements right of the pivot are greater than the pivot

returns pivot's position

*/

int partition (int *A, int left, int right, int pivotIndex, int *comps){

 

/*****************************************/

 

}

 

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

mode 1: pivot=left

mode 2: pivot=random

mode 3: pivot=random + insertionSort

output: A sorted in increasing order

number of comparissons between array elements

*/

void quicksort(int *A, int left, int right, int mode, int *comps){

 

/**********************************/

 

}

 

void displayMatrix(int A[], int length){

int i;

printf("\nTa stoixeia toy pinaka einai: ");

for(i=0; i<length; i++)

printf("%d ", A);

printf("\n");

}

 

//creates the dynamic array and returns its dimension

//pass by reference for the array pointer

int createArray(int **A){

[bokarinho]

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

output: A sorted in increasing order

number of comparissons between array elements

*/

void bubblesort(int *A,int left, int right, int *comps){

 

/*********************************************/

}

 

 

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

output: A sorted in increasing order

number of comparissons between array elements

*/

void insertionsort(int *A, int left, int right, int *comps){

 

/*****************************************/

}

 

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

pivotIndex: the position of pivot element

output: A such that pivot is in its correct (sorted) position,

the elements left of the pivot are smaller or equal to the pivot

the elements right of the pivot are greater than the pivot

returns pivot's position

*/

int partition (int *A, int left, int right, int pivotIndex, int *comps){

 

/*****************************************/

 

}

 

/*

input: A: array of int

left, right: first and last position of array elements A that must be sorted

mode 1: pivot=left

mode 2: pivot=random

mode 3: pivot=random + insertionSort

output: A sorted in increasing order

number of comparissons between array elements

*/

void quicksort(int *A, int left, int right, int mode, int *comps){

 

/**********************************/

 

}

 

void displayMatrix(int A[], int length){

int i;

printf("\nTa stoixeia toy pinaka einai: ");

for(i=0; i<length; i++)

printf("%d ", A);

printf("\n");

}

 

//creates the dynamic array and returns its dimension

//pass by reference for the array pointer

int createArray(int **A){

 

Αυτό γιατί το πόσταρες σκέτο; Για να σου το συνεχίσουμε; Α ζητάω συγγνώμη που ξέχασα να στο ολοκληρώσω. Α ρε τρελα που πουλάτε... Έχετε τύψεις δεν παίζει... Δεν ξέρω μπορεί και να σου έγγραφα κάτι αλλά ένας φίλος από αυτό το φόρουμ με προβλημάτισε. Δεν πρέπει να διαιωνιστεί το είδος..

[asik88]

Φίλε αυτη την ασκηση έχεις ολοκληρώση;

Και έγω έχω ακριβός τη ίδια μπορέις να μου στείλεις???

το e-mail μου ειναι ayhanlam @ hot mail.com

[3c0r1z]

Μέτα απο ένα χρόνο σιγά μην θυμάται το forum