| User info | |
|---|---|
| User name: | Fisher |
| Bio: | Bio: template <class Comparable>
int sequentialSearch(const vector<Comparable> &v, Comparable x) { for (int i = 0; i < v.size(); i++) if (v[i] == x) return i; // encontrou return -1; // não encontrou } ///PESQUISA BINARIA//// template <class Comparable> int binarySearch(const vector<Comparable> &v, Comparable x) { int left = 0, right = v.size() - 1; while (left <= right) { int middle = (left + right) / 2; if (x == v[middle]) return middle; // encontrou else if (x < v[middle]) right = middle - 1; else left = middle + 1; } return -1; // não encontrou } ////ORDENACAO POR INSERCAO//// template <class Comparable> void insertionSort(vector<Comparable> &v) { for (int i = 1; i < v.size(); i++) { Comparable tmp = v[i]; int j; for (j = i; j > 0 && tmp < v[j-1]; j--) v[j] = v[j-1]; v[j] = tmp; } } /////QUICKSORT///// template <class Comparable> void quickSort(vector<Comparable> &v) { quickSort(v,0,v.size()-1); } template <class Comparable> void quickSort(vector<Comparable> &v, int left, int right) { if (right-left <= 20) // se vector pequeno insertionSort(v,left,right); else { Comparable x = median3(v,left,right); // x é o pivot int i = left; int j = right-1; // passo de partição for(; ; ) { while (v[++i] < x); while (x < v[--j]); if (i < j) swap(v[i], v[j]); else break; } swap(v[i], v[right-1]); //repoe pivot quickSort(v, left, i-1); quickSort(v, i+1, right); } } template <class Comparable> Comparable &median3(vector<Comparable> &v, int left, int right) { int center = (left+right) /2; if (v[center] < v[left]) swap(v[left], v[center]); if (v[right] < v[left]) swap(v[left], v[right]); if (v[right] < v[center]) swap(v[center], v[right]); //coloca pivot na posicao right-1 swap(v[center], v[right-1]); return v[right-1]; } template <class Comparable> void insertionSort(vector<Comparable> &v, int left, int right) { for (int i = left+1; i < right+1; i++) { Comparable tmp = v[i]; int j; for (j = i; j > 0 && tmp < v[j-1]; j--) v[j] = v[j-1]; v[j] = tmp; } } |
| History | |
| Joined: | |
| Number of posts: | 2 |
| Latest posts: | |