'CS/Algorithm'에 해당되는 글 2건

  1. 2010.08.03 Quick Sort
  2. 2009.03.10 Tree Traversal

Quick Sort

CS/Algorithm 2010. 8. 3. 04:24
 function quicksort(array, left, right)
     var pivot, leftIdx = left, rightIdx = right
     if right > left // only sort if there are >= 2 elements
         pivot = (left + right) / 2
         while leftIdx <= pivot and rightIdx >= pivot
             while array[leftIdx] < array[pivot] and leftIdx <= pivot
                 leftIdx = leftIdx + 1
             while array[rightIdx] > array[pivot] and rightIdx >= pivot
                 rightIdx = rightIdx - 1;
             swap array[leftIdx] with array[rightIdx]
             leftIdx = leftIdx + 1
             rightIdx = rightIdx - 1
             if leftIdx - 1 == pivot
                 pivot = rightIdx = rightIdx + 1
             else if rightIdx + 1 == pivot
                 pivot = leftIdx = leftIdx - 1
         quicksort(array, left, pivot - 1)
         quicksort(array, pivot + 1, right)
void quick_sort(int arr[], int l, int r)
{
	if (l < r) {
		int i=l, j=r, pivot=l+(r-l)/2;
		while (i < j) {
			while (i < pivot && arr[i] <= arr[pivot]) 
				++i;
			while (j > pivot && arr[j] >= arr[pivot])
				--j;
			swap_arr(arr, i, j);
			++i, --j;
			if (i-1 == pivot)
				pivot = j = j+1;
			else if (j+1 == pivot)
				pivot = i = i-1;
		}
		qsort_2(arr, l, pivot-1);
		qsort_2(arr, pivot+1, r);
	}
}



  // left is the index of the leftmost element of the array
  // right is the index of the rightmost element of the array (inclusive)
  //   number of elements in subarray: right-left+1
  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right] // Move pivot to end
     storeIndex := left 
     for i  from  left to right - 1 // left ≤ i < right 
         if array[i] ≤ pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right] // Move pivot to its final place
     return storeIndex
 procedure quicksort(array, left, right)
     if right > left // subarray of 0 or 1 elements already sorted
         select a pivot index //(e.g. pivotIndex := left + (right - left)/2)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         // element at pivotNewIndex is now at its final position and never moved again
         //   and guarantees termination: recursive calls will sort smaller array
         // recursively sort elements on the left of pivotNewIndex
         quicksort(array, left, pivotNewIndex - 1)
         // recursively sort elements on the right of pivotNewIndex
         quicksort(array, pivotNewIndex + 1, right)


int partition(int arr[], int l, int r, int pivot)
{ int pivot_val = arr[pivot]; int sorted_index = l, i; swap_arr(arr, pivot, r); for (i=l; i < r; ++i) { if (arr[i] <= pivot_val) { swap_arr(arr, i, sorted_index); sorted_index++; } } swap_arr(arr, sorted_index, r); return sorted_index; } void quick_sort(int arr[], int l, int r) { if (l < r) { int pivot = partition(arr, l, r, (l+r)/2); qsort_1(arr, l, pivot-1); qsort_1(arr, pivot+1, r);; } }

:

Tree Traversal

CS/Algorithm 2009. 3. 10. 17:59
To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node:

   1. Visit the root.
   2. Traverse the left subtree.
   3. Traverse the right subtree.

(This is also called Depth-first traversal.)



To traverse a non-empty binary tree in inorder, perform the following operations recursively at each node:

   1. Traverse the left subtree.
   2. Visit the root.
   3. Traverse the right subtree.

(This is also called Symmetric traversal.)



To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node:

   1. Traverse the left subtree.
   2. Traverse the right subtree.
   3. Visit the root.



Finally, trees can also be traversed in level-order, where we visit every node on a level before going to a lower level. This is also called Breadth-first traversal.



Example

In this binary search tree,

Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root,left child,right child)
Inorder traversal sequence: A, B, C, D, E, F, G, H, I (leftchild,rootnode,right node)
Note that the inorder traversal of this binary search tree yields an ordered list
Postorder traversal sequence: A, C, E, D, B, H, I, G, F (leftnode,rightnode,rootnode)
Level-order traversal sequence: F, B, G, A, D, I, C, E, H

원문 : http://en.wikipedia.org/wiki/Tree_traversal

: