#include <stdio.h>
void trimspace(char \*dst) {
const char \*src = dst;
int tocopy = 1;
char c;
while((c = \*src++)) {
if(tocopy)
\*dst++ = c;
tocopy = (c != ' ') || (\*src != ' ');
}
\*dst = '\\0';
}
int main() {
char s\[64\];
scanf("%\[^\\n\]c", s);
trimspace(s);
printf("%s\\n", s);
}
Word Length Frequency
// word\_len\_histo.cpp : reads words and lists distribution // of word lengths. // Fred Swartz, 2002-09-01 // This would be nice to turn into an OO program, where // a class represented a distribution of values. // Some elements which are globals here would turn into // private member elements in the class (eg, valueCount). //--- includes #include <iostream> #include <iomanip> #include <cctype> using namespace std; //--- prototypes void countValue(int cnt); float getAverage(); //--- constants const int BINS = 21; // how many numbers can be counted //--- globals int valueCount\[BINS\]; // bins used for counting each number int totalChars = 0; // total number of characters //=========================================================== main int main() { char c; // input character int wordLen = 0; // 0 if not in word, else word length //--- Initialize counts to zero for (int i=0; i valueCount\[i\] = 0; } //--- Read chars in loop and decide if in a word or not.
[Read More]
Reading from file or Reading integers from file
#include
#include
#include
#include
using namespace std;
int main() {
int sum = 0;
int x;
ifstream inFile;
inFile.open(“integers.txt”); // read integers from text file
if (!inFile) {
cout « “Unable to open file”;
exit(0); // terminate with error
}
while (inFile » x) {
sum = sum+x;
}
inFile.close();
cout « “Sum = " « sum « endl;
return 0;
}
Hirschberg’s linear space algorithm in C++
It should work on any container type which supports forward and reverse iteration. It’s similar to the Python implementation, but note:
rather than copy slices of the original sequences, it passes around iterators and reverse iterators into these sequences rather than recursively accumulating sums of sub-LCS results, it ticks off items in a members array, xs_in_lcs /\* C++ implementation of "A linear space algorithm for computing maximal common subsequences" D.
[Read More]
Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort
in your Pseudocode, the if condition should be if …
RM - May 3, 2014
in your Pseudocode, the if condition should be if (low < high).
Thanks Rish. I have made the change a[low] > a[high] rather than low < low. :). Thanks for correcting me.
Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort
Problem Sort a binary array - array containing 0s and 1s in 1 pass. This is also called two color sort.
Example Input - Binary unsorted array
A = {0,1,1,0,0,1};
Output - binary sorted array
B = {0,0,0,1,1,1}
Solution This is similar to quicksort partition algorithm. Though normal sorting takes O(n log n) time, but we have to just partition 0 from 1, and hence it should only take time of partitioning - O(n).
[Read More]
Bubble sort
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
What is Bubble Sort?
The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order).
[Read More]
Quick sort
Hoore cisca discovered it in 1961.
Why quicksort?
Definitely a greatest hit algorithm Prevalent in practice O(n log n) time “on average” minimal extra memory needed (which gives it leverage over merge sort) The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
Quicksort helps us solving this problem.
What is quick sort?
[Read More]
Radix sort
What is radix sort?
Radix Sort is an algorithm that sorts a list of numbers and comes under the category of distribution sort.
This sorting algorithm doesn’t compare the numbers but distributes them, it works as follows:
1. Sorting takes place by distributing the list of number into a bucket by passing through the individual digits of a given number one-by-one beginning with the least significant part. Here, the number of buckets are a total of ten, which bare key values starting from 0 to 9.
[Read More]
Merge Sort
Mergesort is one of the older algorithms known since 1945. It is very good example of divide and conquer paradigm and is better than other simpler sort algorithms like selection, insertion or bubble sort.
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
So, merge sort algorithm is a recursive algorithm which calls itself on the smaller problem set.
[Read More]