C++ :: Insertion Sort Algorithm With Comparison Counter
Nov 7, 2013
So I have an insertion sort function implemented that sorts through an array, but I'm having a problem showing the correct number of comparisons to work.
Each time I'm checking a value with another, the counter should update.
For instance, having an array of 10 elements going from 10-1 should give 45 comparisons, but I'm getting 54 comparisons.
void insertionSort(int a[], int& comparisons, const int& numOfElements) {
int j, value;
for (int i = 1; i < numOfElements; i++) {
value = a[i];
for (j = i - 1; j >= 0 && a[j] > value; j--)
Suppose you have defined a container of elements and you want do define a comparison function between elements based on the ordering of the elements in that container. What algorithm for the comparison would be the most efficient?
My current idea is to simply iterate from the beginning of the container, and whichever of the two elements is found first is the lesser (assuming the second is not the same as the first). It seems kind of naïve though. Any better performing algorithm? This is what I have so far:
Would perhaps forcing the container to have a random access iterator, like vector, and then writing a specialized comparison function based on that perform even faster? Or perhaps force the container to be a map to integers, and compare the elements by comparing the integer mapped values?
This program I'm working on accepts an array size from the user, prompts the user to store that many integers, sorts them from smallest to largest, and then searches for duplicates with a simple for loop. The ultimate goal of the assignment was to display duplicates in an array, and the rest of the functions are just how I decided to reach that goal.
Anyway, my program crashes if I choose an array size larger than 7. It sorts and displays duplicates perfectly with 7 or fewer arguments.
The exact moment it crashes is after I enter the final value it prompts me for, so it appears my inputsize() function and my inputarray() function are working, and the error may be in the arrsort() function. Code is below:
Code: #include <stdio.h> int funcinputsize(int); void funcinputarray(int [], int size); void funcarrsort(int [], int size); void funcdupe(int [], int size);
I am having trouble sorting out a list of names in c. I have code for sorting the names, but when I go to print them out they still are in the same order as they were at the beginning so something isnt right. So the function that I need is the sort_data function.
matt susan mark david aden phil erik john caden mycah
So I need to get this list in alphabetical order, but when I run my code and print out this list after I run the sort function, they are still in this order.
This program using the selection, insertion, and bubble sorts. The program needs to be able to do the following:
1. Create an array of 1000 population records when the array object is instantiated. Call it unSorted.
2.Open the file called "Population.csv" (on the portal) and invoke a function that loads the population data into the array.
3.Create a second array of 1000 elements that will be used to sort the data using the different algorithms. Name is sortedArray.
4.Write a function that will copy unSorted into sortedArray and execute that function.
5.Using a function, display the unsorted array.
6.Invoke the insertionSort () function that will sort the sortedArray using the insertion sort algorithm. Sort the population data on the rank field in ascending order. Alternatively, you can sort in descending order on population.
7.Using the display function, display sortedArray.
8.Display the number of iterations it took to do the sort using this algorithm.
9.Repeat steps 4-8 for the selection and bubble sort algorithms.
Here is my code so far:
Code: #include <iostream> #include <iomanip> #include <fstream> using namespace std; void loadArray (int unSorted[], int s); void displayArray (const int num [], int size);
[Code] .....
Here is a few lines from the Population.csv file contents:
I'm not sure how to load the data from the file into the array properly, I attempted this. I also don't know how to copy the unSorted into sortedArray.
So i'm trying to implement the selection sort algorithm and it seems that the code is fine but...
Code: #include <cs50.h> #include "helpers.h" void sort(int values[], int n) { // TODO: implement an O(n^2) sort
[Code] ....
I keep getting these errors and i don't understand why:
/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu/crt1.o: In function `_start': (.text+0x20): undefined reference to `main' collect2: ld returned 1 exit status
I'm trying to implement the Merge-Sort algorithm. I only had the pseudocode for it and have some problems coding this into C.
I have only covered pointers recently and I tried using them, which did not work. I started with the code for the merge algorithm and only used a 10 element array, which was already divided into two sorted subarrays:
Code: #include <stdio.h>#include <stdlib.h> int main() { int a[5]={1,5,6,10,13}, b[5]={4,8,9,10,14},c[10], *i,*j,k;
[Code].....
This is the result that I get:
Code: 1 4 5 6 8 9 10 10 13 0
So I think the problem occurs because in the second to last loop i is incremented again, but the end of the array is already reached, and the compiler has no element a[6] to compare with *j in the last run of the loop. Is there generally a better way to implement Merge?
I'm tinkering with a serial quick sort algorithm. Normally I use qsort() but I wanted to test this.
Somehow I loose the highest number. I can't see where I drop it.
Code: // function to quicksort, leave them in front of qsort. void swap(float_t *left, float_t *right){ float_t temp; temp = *left; *left = *right; *right = temp;
I've written code for a selection sort algorithm to sort through a singly linked list, However, it only brings the smallest node to the front, but doesnt swap positions of any of the remaining nodes, even though they are not in order.
I developed the following heap sort algorithm code, and for some reason anytime it goes above 4100 entries, the algorithm completely crashes. It works perfectly up until that point but I can't see why it would crash?
void heap_from_root(MVector &v, int i, int n) { int end=n,j=0; // Identify the lowest root and how many sons it has. If it only has one son, set j=1. if (n==1) { n = 0; j = 1; } else if ((n-2) % 2 == 0) { n = (n-2)/2; } else if ((n-1) % 2 == 0) { n = (n-1)/2; j=1; }
This program is sorting a randomized array of integers using the bubblesort algorithm.
I am trying to modify n correct the source code,so that the swapping of two values will be done by a function called swap values() by using call-by-reference but function should have as arguments only the two array elements that must be exchanged. (Note: do not pass the whole array to the function!) .We consider an array with the first element containing the number of elements in the array, followed by 10 randomly initialized integers (elements).
The code must sort the 10 elements in ascending order.
Compile: g++ -Wall sorting.cpp -o sorting */ #include <iostream> #include <stdlib.h> using namespace std; int main() { const int SIZE=10;
C++ sort algorithm or library that can take input of a bunch of rows of data and then sort rows by an arbitrary defined order of one of the columns ... i.e., sort rows by value of the first column in this order (boba bobc bobe bobx) etc?
I know that the getline() can have a deliminator parameter but since there is no commas should I put an newline deliminator? Would that be ? And I know that the insert() function works.
I am working with A.V.L. trees at the moment and I have to implement a program that inserts a node and if needed re-balance the tree.I have problems when I have to do a double rotation because after I insert a node the tree is messed up. This is a picture with what my program shows after i run it. [URL] .....
void length(NodeT* p,int *maxi,int l) { if (p!=NULL) { length(p->left,&*maxi,l+1); if ((p->left==NULL)&&(p->right==NULL)&&(*maxi<l)) *maxi=l; length(p->right,&*maxi,l+1);
Suppose multiple threads are are trying to insert into a STL Map, both are trying to insert with same key. As per my understanding it will not cause any issue till you invalidate the iterator. Here as per me it will not invalidate the iterator.
Example radix sort function to sort an array of 64 bit unsigned integers. To allow for variable bin sizes, the array is scanned one time to create a matrix of 8 histograms of 256 counts each, corresponding to the number of instances of each possible 8 bit value in the 8 bytes of each integer, and the histograms are then converted into indices by summing the histograms counts. Then a radix sort is performed using the matrix of indices, post incrementing each index as it is used.
Code: typedef unsigned long long UI64; typedef unsigned long long *PUI64; PUI64 RadixSort(PUI64 pData, PUI64 pTemp, size_t count) { size_t mIndex[8][256] = {0}; /* index matrix */ PUI64 pDst, pSrc, pTmp; size_t i,j,m,n; UI64 u;
I have been working on a program that records the time it takes the user to complete a maze. The user's time is then recorded and inserted into a linked list of structures based on the time (from quickest time to longest). I wrote some code that does this, but I was wondering if I can make the code more concise/make sense -- like only using two pointers or having less if statements.Here is a struct that are the elements of the linked list (I also have a global variable to keep track of the head of the list:
